These authors contributed equally to this work.

These authors contributed equally to this work.

1]School of Mathematical Sciences, University of Nottingham, Nottingham, NG7
2RD, UK

2]Centre for the Mathematics and Theoretical Physics of Quantum Non-
Equilibrium Systems, University of Nottingham, Nottingham, NG7 2RD, UK

3]Department of Mathematics, Politecnico di Milano, Piazza L. da Vinci 32,
Milan, 20133, Italy

4]School of Physics and Astronomy, University of Nottingham, Nottingham, NG7
2RD, UK

# Bounds on Fluctuations of First Passage Times for Counting Observables in
Classical and Quantum Markov Processes

George Bakewell-Smith  Federico Girotti  Mădălin Guţă  Juan P. Garrahan  [  [
[  [

###### Abstract

We study the statistics of first passage times (FPTs) of trajectory
observables in both classical and quantum Markov processes. We consider
specifically the FPTs of counting observables, that is, the times to reach a
certain threshold of a trajectory quantity which takes values in the positive
integers and is non-decreasing in time. For classical continuous-time Markov
chains we rigorously prove: (i) a large deviation principle (LDP) for FPTs,
whose corollary is a strong law of large numbers; (ii) a concentration
inequality for the FPT of the dynamical activity, which provides an upper
bound to the probability of its fluctuations to all orders; and (iii) an upper
bound to the probability of the tails for the FPT of an arbitrary counting
observable. For quantum Markov processes we rigorously prove: (iv) the quantum
version of the LDP, and subsequent strong law of large numbers, for the FPTs
of generic counts of quantum jumps; (v) a concentration bound for the the FPT
of total number of quantum jumps, which provides an upper bound to the
probability of its fluctuations to all orders, together with a similar bound
for the sub-class of quantum reset processes which requires less strict
irreducibility conditions; and (vi) a tail bound for the FPT of arbitrary
counts. Our results allow to extend to FPTs the so-called “inverse
thermodynamic uncertainty relations” that upper bound the size of fluctuations
in time-integrated quantities. We illustrate our results with simple examples.

###### keywords:

Classical Markov chains, quantum Markov processes, Counting observables, First
passage times, Large deviations, Concentration bounds, Thermodynamic
uncertainty relations

##  1 Introduction and Summary of Results

The evolution of most physical systems, whether they be classical or quantum,
is characterised by fluctuations owing to their interaction with the
environment [1, 2, 3, 4, 5]. The study of such dynamical fluctuations in
stochastic systems is of central importance for several reasons. On a
practical note, fluctuations have a significant impact on the estimation
precision of unknown parameters of the dynamics and on the performance of a
system for practical uses, such as in heat engines, mechanical and biological
clocks, biological motors, or quantum machines. On a conceptual level,
quantifying the probabilities of fluctuations away from typical behaviour
allows to systematically classify and explain the properties of the dynamics.

In a stochastic system the main quantities of interest are time-integrated
observables of the trajectories of the dynamics, both of time-asymmetric
quantities such as particle and energy currents [4, 5], and of time-symmetric
quantities such as dynamical activities [6, 7, 8, 9], or their quantum
analogues such as counts of emissions into the environment [10, 3]. The
statistics of these can be quantified using the tools of the theory of large
deviations (LD) [11, 12], which in turn allows one to define an ensemble
method (akin to the configuration ensemble method of equilibrium statistical
mechanics) for stochastic trajectories, with the associated concept of
(dynamical) phases and (dynamical) phase transitions [6, 8, 13, 14, 15].
Closely related to time-integrated quantities are their first passage times
(FPTs) [16], i.e., the times it takes for the observable to reach a certain
fixed threshold. Trajectory ensembles can also be studied in terms of FPTs
using LD methods [17, 18].

A class of fundamental results for trajectory observables are so-called
thermodynamic uncertainty relations (TURs) [19, 20]. In their broadest
acceptation, TURs are general lower bounds on the probability of fluctuations
of time-integrated trajectory observables, expressed in terms of global
quantities such as entropy production or dynamical activity. The importance of
TURs stems from the fact that they point out fundamental physical limitations,
for example that larger precision of estimation (implying smaller
fluctuations) can only be attained at the cost of higher entropy production
and/or higher dynamical activity. Just like for time-integrated quantities, a
form of the TUR also provides lower bounds to the probabilities of
fluctuations of FPTs [21, 22]. For a sample of the by now large literature on
TURs see for example [23, 24, 25, 26, 27, 28, 29, 30, 31, 32, 33, 34, 35, 36,
37, 38, 39, 40, 41] and for a review [42].

In contrast to the lower bounds of the TUR, in recent works [43, 44] we
addressed the problem of formulating general upper bounds to the probability
of fluctuations of time-integrated quantities in both classical [43] and
quantum [44] stochastic systems using concentration techniques. We called
these bounds “inverse TURs” (iTUR) [43]. Together with the TUR, the iTUR
provides a range that limits the probability of observing a fluctuation away
from the average (and not just a one-sided bound). In fact, we showed in [43]
that the iTUR can often be a tighter bound than the TUR. This can offer an
advantage for estimation, which is countered by the fact that while the iTUR
also depends on general features of the system (relaxation time, shortest
time-scale) it is not as operationally accessible as the TUR.

In this paper we extend these upper bounds (or iTURs) to the FPTs of counting
observables, i.e. quantities corresponding to the accumulated number of
changes of the state of the system along time. We derive these upper bounds on
FPTs for both classical and quantum stochastic systems. Anticipating the
notation that we will define in detail below, if $\mathfrak{E}$ indicates the
set of all possible jumps given the dynamics (all possible transitions between
configurations in the classical case, or all possible dissipative events in
the quantum case) and $\mathfrak{A}\subseteq\mathfrak{E}$ the subset of jumps
that we are interested in, let $K_{\mathfrak{A}}(t)$ be the associated
stochastic process that counts the number of jumps belonging to $\mathfrak{A}$
that occur in a stochastic trajectory up to time $t$. The FPT at level
$k\in\mathbb{N}$, which we denote $T_{\mathfrak{A}}(k)$, is the time at which
$K_{\mathfrak{A}}(t)$ reaches the value $k$ for the first time. For example,
consider a quantum system whose state evolves according to a quantum Markov
semigroup coupled to several “emission channels”: when the experimenter
performs continuous-time counting of measurements in each of these channels
they observe a random sequence of clicks from the sensors; the FPT
$T_{\mathfrak{A}}(k)$ is when the count of the clicks of interest reaches $k$.
(Throughout we assume the dynamics to be irreducible which implies the
existence of a unique stationary state.)

This paper presents two sets of results. The first set is for the FPTs in
classical systems evolving with continuous-time Markov dynamics. The second
set of results generalises the classical ones to continuous-time quantum
Markov chains. Our results below can be summarised as follows:

(i) We show rigorously that the FPTs of classical counting observables,
$T_{\mathfrak{A}}^{c}(k)$, satisfy a large deviation principle or LDP (Theorem
2 below), which, loosely speaking, means that (cf. [17, 21])

$\mathbb{P}\left(\frac{T^{\rm c}_{\mathfrak{A}}(k)}{k}=dt\right)\asymp
e^{-kI^{\rm c}_{\mathfrak{A}}(dt)},$

(where the label “c” stands for “classical”) for a non-negative generalised
function $I^{\rm c}_{\mathfrak{A}}$, called the LD rate function. $I^{\rm
c}_{\mathfrak{A}}$ admits a unique minimum in $\langle
t_{\mathfrak{A}}\rangle_{\rm c}$, where it vanishes. This fact, together with
some regularity properties of the rate function, implies the strong law of
large numbers:

$\lim_{k\rightarrow+\infty}\frac{T^{\rm c}_{\mathfrak{A}}(k)}{k}=\langle
t_{\mathfrak{A}}\rangle_{\rm c}\quad{\rm a.s.}.$

One can see that $\langle t_{\mathfrak{A}}\rangle_{\rm c}$ is the expected
time that it takes to observe a jump in $\mathfrak{A}$ in the stationary
regime. The law of large numbers states that $T^{\rm c}_{\mathfrak{A}}(k)/k$
converges a.s. to some asymptotic value and the LDP ensures that fluctuations
away from that value decay exponentially fast in the threshold $k$. Notice
that these are statements asymptotic in $k$.

(ii) Building on the above, we prove an upper bound for the probability of
fluctuations of the FPT of the dynamical activity away from the asymptotic
limit and for any finite threshold $k$ in the form of a concentration bound
(Theorem 3 below)

$\max\left\\{\mathbb{P}\left(\frac{T^{\rm c}_{\mathfrak{E}}(k)}{k}\geq\langle
t_{\mathfrak{E}}\rangle_{\rm c}+\gamma\right),\mathbb{P}\left(\frac{T^{\rm
c}_{\mathfrak{E}}(k)}{k}\leq\langle t_{\mathfrak{E}}\rangle_{\rm
c}-\gamma\right)\right\\}\leq e^{-k\hat{I}^{\rm c}_{\mathfrak{E}}(\gamma)},$

for some bounding function $\hat{I}^{\rm c}_{\mathfrak{E}}$ that depends on
general properties of the dynamics.

(iii) We also prove a more general tail bound for right deviations, valid for
every $k$ and for any kind of counting observable (not just the activity) in
the form of a concentration bound (Theorem 5)

$\mathbb{P}\left(\frac{T^{\rm c}_{\mathfrak{A}}(k)}{k}\geq\langle
t_{\mathfrak{A}}\rangle_{\rm c}+\gamma\right)\leq e^{-k\tilde{I}^{\rm
c}_{\mathfrak{A}}(\gamma)},$

for every $\gamma\geq\overline{\gamma}\geq 0$, where $\overline{\gamma}$ is a
constant depending on $\mathfrak{A}$ and on the largest average FPT of the
system111 A quantity with an analogous meaning appears in some recent bounds
obtained for the empirical time to reach a particular state in classical
Markov processes [45]. , and where the bounding function $\tilde{I}^{\rm
c}_{\mathfrak{A}}$ is expressed in terms of general properties of the
dynamics.

(iv) We prove rigorously that the distribution of FPTs of counts of quantum
jumps, $T_{\mathfrak{A}}^{q}(k)$, also obeys a LDP (10),

$\mathbb{P}\left(\frac{T^{\rm q}_{\mathfrak{A}}(k)}{k}=dt\right)\asymp
e^{-kI^{\rm q}_{\mathfrak{A}}(dt)},$

(where the label “q” stands for “quantum”) with rate function $I^{\rm
q}_{\mathfrak{A}}$ which vanishes at its unique minimum $\langle
t_{\mathfrak{A}}\rangle_{\rm q}$. The strong law of large numbers follows,

$\lim_{k\rightarrow+\infty}\frac{T^{\rm q}_{\mathfrak{A}}(k)}{k}=\langle
t_{\mathfrak{A}}\rangle_{\rm q}\quad{\rm a.s.},$

with $\langle t_{\mathfrak{A}}\rangle_{\rm c}$ the expected time that it takes
to observe a quantum jump in $\mathfrak{A}$.

(v) For the case where the observable is the count of all quantum jumps, we
prove the existence of a concentration bound for fluctuations of all orders of
the corresponding FPT valid for all $k$, i.e., a quantum analogue of the
classical result (ii)

$\max\left\\{\mathbb{P}\left(\frac{T_{\mathfrak{E}}^{\rm q}(k)}{k}\geq\langle
t_{\mathfrak{E}}\rangle_{\rm
q}+\gamma\right),\mathbb{P}\left(\frac{T_{\mathfrak{E}}^{\rm
q}(k)}{k}\leq\langle t_{\mathfrak{E}}\rangle_{\rm
q}-\gamma\right)\right\\}\leq e^{-k\hat{I}^{\rm q}_{\mathfrak{E}}(\gamma)},$

where the bounding function $\hat{I}^{\rm q}_{\mathfrak{E}}$ depends on
general properties of the dynamics. We prove this for generic quantum Markov
chains (Theorem 11) which requires a stronger irreducibility assumption on the
dynamics than in the classical case (Hypothesis 3). We also prove a more
specific concentration bound for the total count in quantum reset processes
(Theorem 13) which requires a less stringent irreducibility condition
(Hypothesis 2).

(vi) We prove a tail bound for right deviations of the FPT $T^{\rm
q}_{\mathfrak{A}}(k)$ of a generic quantum jump count for every $k$

$\mathbb{P}\left(\frac{T^{\rm q}_{\mathfrak{A}}(k)}{k}\geq\langle
t_{\mathfrak{A}}\rangle_{\rm c}+\gamma\right)\leq e^{-k\tilde{I}^{\rm
q}_{\mathfrak{A}}(\gamma)},$

valid for $\gamma\geq\overline{\gamma}\geq 0$, where $\overline{\gamma}$
depends on $\mathfrak{A}$ and on the largest average FPT of the system
(Theorem 15).

The proof of every bound we derive below goes through Chernoff’s inequality
([46, Section 2.2]) and is obtained upper bounding the corresponding moment
generating function (MGF) of the FPTs. Easy corollaries are upper bounds of
the variance of the FPTs for every value of $k$ in the stationary regime. This
complements the lower bounds to probability of fluctuations given by the TURs,
previously obtained in the form of upper bounds on the rate functions or on
the relative precision [21, 47, 40, 48].

The rest of the manuscript is organised as follows. The main text is split
into two parts: Sec. 2 focuses on classical Markov processes, while Sec. 3
focuses on quantum Markov processes. For the classical case, we introduce
notation, definitions, existing and preliminary results in Subsec. 2.1. The
LDP for classical FPTs is presented in Subsec. 2.2.1, the classical
concentration inequality for the FPT of the activity in Subsec. 2.2.2, and the
FPT tail bound in Subsec. 2.2.3. For quantum Markov processes we introduce
notation, definitions and previous results in Subsec. 3.1. The LDP for FPT of
quantum jump counts is presented in Subsec. 3.2.1, the concentration bound for
the FPT of total number of counts in Subsec. 3.2.2, the FPT of the total count
in quantum reset processes Subsec. 3.2.3, and the tail bound for the FPT of
more general quantum counting processes in Subsec. 3.2.4. In Sec. 4 we provide
our conclusions. The Appendices contain the proofs of the new theorems and
lemmas presented in the main text.

##  2 Large Deviation Principle and Concentration Bounds for FPTs in Classical
Markov Processes

In this Section we begin by recalling the necessary notions regarding
classical Markov chains, introducing notation and stating the assumptions that
we make in this paper. In particular, we define first passage times (FPTs)
corresponding to counting observables, that is, time-additive observables of
trajectories which are non-decreasing (in contrast to currents), cf. [21].
After that, we prove that the sequence of FPTs satisfies a Large Deviation
Principle [11] and we provide an expression for the rate function (the scaled
logarithm of the probability). Then, we provide an upper bound on the
fluctuations of the FPT for the dynamical activity [8, 9], and a tail bound
for FPTs for generic counting observables. We illustrate our results with
simple models, and in particular we discuss the behaviour of the bound for the
FPT corresponding to the dynamical activity when the system is at conditions
of metastability, i.e., near a first-order phase crossover.

###  2.1 Preliminaries and Notation

Let us consider a continuous-time Markov chain $X:=(X_{t})_{t\geq 0}$ taking
values in a finite configuration space $E$. For an initial distribution $\nu$
over configurations we denote by $\mathbb{P}_{\nu}$ the corresponding law of
the process $X$ and $\mathbb{E}_{\nu}$ its integral. The stochastic generator
of $X$ has the form:

$\mathbf{L}=\mathbf{W}-\mathbf{R},$

where the off-diagonal part, $\mathbf{W}=\sum_{x\neq y}w_{xy}\ket{x}\bra{y}$,
encodes the rates of jumps (with $w_{xy}$ the transition rate from
configuration $x$ to configuration $y$), and the diagonal part,
$\mathbf{R}=\sum_{x}R_{x}\ket{x}\bra{x}$, the escape rates (with
$R_{x}=\sum_{y}w_{xy}$ the escape rate from configuration $x$). The generator
$\mathbf{L}$ acts on complex valued functions $f:E\rightarrow\mathbb{C}$ via
right multiplication, i.e.,

$f(x)\mapsto(\mathbf{L}f)(x)=\sum_{y\in
E}\mathbf{L}_{xy}f(y)=\mathbb{E}_{\delta_{x}}[f(X_{1})],$

which is similar to the “Heisenberg picture” in quantum mechanics. The natural
norm to consider in this setting is the $\infty$-norm, i.e.

$\|f\|_{\infty}:=\max_{x\in
E}|f(x)|,\quad\|\mathbf{L}\|_{\infty\rightarrow\infty}:=\max_{\|f\|_{\infty}=1}\|\mathbf{L}f\|_{\infty}.$

By duality, $\mathbf{L}$ acts also on complex valued measures on $E$ (which
can be identified with their density $\nu:E\rightarrow\mathbb{C}$) via left
multiplication (cf. Schrödinger picture in quantum mechanics):

$\nu(x)\mapsto(\mathbf{L}_{*}\nu)(x):=(\nu\mathbf{L})(x)=\sum_{y\in
E}\nu(y)\mathbf{L}_{yx}=\mathbb{P}_{\nu}(X_{1}=x).$

Here the natural norm is the dual norm with respect to the $\infty$-norm,
which is the $1$-norm:

$\|\nu\|_{1}:=\sum_{x\in E}|\nu(x)|,\quad\|\mathbf{L}_{*}\|_{1\rightarrow
1}:=\max_{\|\nu\|_{1}=1}\|\mathbf{L}_{*}\nu\|_{1}=\|\mathbf{L}\|_{\infty\rightarrow\infty}.$

We will often use the notation $\langle\nu,f\rangle$ to denote the integral of
$f$ with respect to $\nu$, i.e. $\sum_{x\in E}\nu(x)f(x).$ We state below our
main assumption for classical dynamics.

######  Hypothesis 1 (Irreducibility of $\mathbf{L}$).

There exists a unique fully supported measure $\hat{\pi}$ satisfying
$\hat{\pi}\mathbf{L}=0$.

The process $X$ can be equivalently described in terms of the corresponding
jump process and holding times: indeed any trajectory takes the form of a
sequence

$\omega=\\{(x_{0},t_{0}),(x_{1},t_{1}),(x_{2},t_{2}),\cdots,(x_{k},t_{k}),\dots\\},$

where $x_{i}$ is the state of the system before the $i$-th jump and $t_{i}$ is
the time between the $(i-1)$-th and the $i$-th jump (we set $t_{0}=0$). The
process describing the different states of the system along time (jump
process) is a discrete time Markov process with transition matrix given by

$\mathbf{P}=\mathbf{R}^{-1}\mathbf{W}$ (1)

(notice that due to irreducibility, $R_{x}>0$ for every $x\in E$). If
$\mathbf{L}$ is irreducible, then $\mathbf{P}$ is irreducible too. Indeed

$\begin{split}\hat{\pi}\mathbf{L}=0\Leftrightarrow\hat{\pi}\mathbf{W}=\hat{\pi}\mathbf{R}\Leftrightarrow\hat{\pi}\mathbf{R}\mathbf{P}=\hat{\pi}\mathbf{R}\end{split}$

and $\hat{\pi}\mapsto\hat{\pi}\mathbf{R}$ is a positive linear bijection.
Therefore the unique invariant measure of $\mathbf{P}$, denoted $\pi$ is
related to the invariant measure of the continuous-time generator by

$\pi=\frac{\hat{\pi}\mathbf{R}}{\langle\hat{\pi},\mathbf{R}\underline{1}\rangle}$
(2)

where $\underline{1}$ stands for the function identically equal to $1$.
Irreducibility of the dynamics means that $\pi$ has full support. Conditional
to the jump process, the holding times $t_{i}$ are independent and $t_{i}$
(for $i\geq 1$) is exponentially distributed with parameter $R_{x_{i-1}}$.

In practical applications one might be able to observe only certain jumps of
the trajectory: we denote by $K_{xy}(t)$ the process that counts the number of
transitions $x\to y$ up to time $t$, and more generally, given a nonempty
subset $\mathfrak{A}$ of the set of possible jumps
$\mathfrak{E}:=\\{(x,y):x,y\in E:w_{xy}>0\\}$, we denote

$K_{\mathfrak{A}}(t)=\sum_{(x,y)\in\mathfrak{A}}K_{xy}(t)$

the stochastic process that counts the number of jumps in $\mathfrak{A}$ up to
time $t$. The dynamical activity, or total number of jumps, is the observable
corresponding to $\mathfrak{A}=\mathfrak{E}$. The first passage time (FPT),
$T_{\mathfrak{A}}(k)$ for a trajectory observable $K_{\mathfrak{A}}$
corresponding to the value $k\in\mathbb{N}$ is defined as:

$T_{\mathfrak{A}}(k)=\inf_{t\geq 0}\\{t:K_{\mathfrak{A}}(t)=k\\}.$ (3)

In particular, the first passage time for the total activity corresponding to
the level $k$ is given by the sum of the first $k$ holding times:

$T_{\mathfrak{E}}(k)=\sum_{i=1}^{k}t_{i}.$ (4)

Using the properties of the holding times described above, one finds that the
moment generating function (MGF) of $T_{\mathfrak{E}}(k)$ is well defined for
$u<R_{\min}:=\min_{x}R_{x}$ and is given by

$\mathbb{E}_{\nu}[e^{uT_{\mathfrak{E}}(k)}]=\left\langle\nu,\left(\frac{\mathbb{\mathbf{R}}}{\mathbf{R}-u}\mathbf{P}\right)^{k}\underline{1}\right\rangle=\left\langle\nu,\left(\frac{{\bf
1}}{\mathbf{R}-u}\mathbf{W}\right)^{k}\underline{1}\right\rangle.$ (5)

An analogous formula can be found for every counting observable of the type in
Eq. (3). First of all, it is useful to consider the following splitting of the
evolution generator $\mathbf{L}$:

$\mathbf{L}=\mathbf{W}_{1}+\underbrace{\mathbf{W}_{2}-\mathbf{R}}_{\mathbf{L}_{\infty}},$
(6)

where $\mathbf{W}_{1}$ holds the rates of transitions in $\mathfrak{A}$ and
$\mathbf{W}_{2}$ the rates of transitions not in $\mathfrak{A}$. Notice that
we can always write the first passage time corresponding to the level $k$ as a
sum of times between subsequent jumps in $\mathfrak{A}$:

$T_{\mathfrak{A}}(k)=\sum_{i=1}^{k}s_{i},\quad
s_{i}:=T_{\mathfrak{A}}(i)-T_{\mathfrak{A}}(i-1).$

The process $Y=(y_{0},\dots,y_{k},\dots)$ determined by the state of the
system at the sequence of times $\\{T_{\mathfrak{A}}(k)\\}_{k=0}^{+\infty}$ is
a discrete time Markov process with transition matrix given by

$\mathbf{Q}:=-\frac{{\bf 1}}{\mathbf{L}_{\infty}}\mathbf{W}_{1}.$ (7)

Indeed, using that $\mathbf{L}_{\infty}=\mathbf{W}_{2}-\mathbf{R}$, we can
write

$-\frac{{\bf 1}}{\mathbf{L}_{\infty}}=\frac{{\bf
1}}{\mathbf{R}-\mathbf{W}_{2}}=\frac{{\bf 1}}{{\bf
1}-\mathbf{R}^{-1}\mathbf{W}_{2}}\frac{{\bf 1}}{\mathbf{R}}=\sum_{k\geq
0}\left(\frac{{\bf 1}}{\mathbf{R}}\mathbf{W}_{2}\right)^{k}\frac{{\bf
1}}{\mathbf{R}},$ (8)

and therefore

$\mathbf{Q}=\sum_{k\geq 0}\left(\frac{{\bf
1}}{\mathbf{R}}\mathbf{W}_{2}\right)^{k}\frac{{\bf
1}}{\mathbf{R}}\mathbf{W}_{1}.$ (9)

Since $\mathbf{R}^{-1}\mathbf{W}_{1}$ and $\mathbf{R}^{-1}\mathbf{W}_{2}$ are
the sub-Markov operators that encode the probabilities of jumps which do and
do not, respectively, belong to $\mathfrak{A}$, Eq. (9) expresses the fact
that the probability of the jump $x\to y$ for the process $Y$ is obtained by
summing up the probabilities of all possible trajectories of the jump process
associated to $X$ that start in $x$, arrive in a state $z$ such that
$(z,y)\in\mathfrak{A}$ by using only jumps in $\mathfrak{A}^{C}$, and then
jump from $z$ to $y$. Integrating over all such possible paths, one can also
show that for every $u<\overline{\lambda}:=-\max\\{\Re(z):z\in{\rm
Sp}(\mathbf{L}_{\infty})\\}$, the MGF of $T_{\mathfrak{A}}(k)$ can be written
as:

$\begin{split}\mathbb{E}_{\nu}[e^{uT_{\mathfrak{A}}(k)}]&=\left\langle\nu,\left(\frac{\mathbf{L}_{\infty}}{u+\mathbf{L}_{\infty}}\mathbf{Q}\right)^{k}\underline{1}\right\rangle.\end{split}$
(10)

We remark that for suitable choices of initial distributions and for finite
$k$’s, $\mathbb{E}_{\nu}[e^{uT_{\mathfrak{A}}(k)}]$ might be well defined even
for some values of $u$ bigger or equal than $\overline{\lambda}$; nevertheless
Theorem 2 shows that in the large $k$ limit, the only values which play a
nontrivial role are $u<\overline{\lambda}$.

For the case of dynamical activity, we have already mentioned that
$\mathbf{Q}=\mathbf{P}$ is irreducible; more generally, $\mathbf{Q}$ is only
irreducible on the subspace $\\{y\in E:\exists x\in
E:\,(x,y)\in\mathfrak{A}\\}$, the complement of which is transient. Indeed,
$\mathbf{Q}$ admits as unique invariant measure

$\varphi=\frac{\hat{\pi}\mathbf{W}_{1}}{\langle\hat{\pi},\mathbf{W}_{1}\underline{1}\rangle},$
(11)

which, in general, is not fully supported.

From the expression of the moment generating function, using standard theory
(see the Theorem 2 below) one obtains that under $\mathbb{P}_{\nu}$ (for every
initial law $\nu$) the following convergence holds true almost surely:

$\frac{T_{\mathfrak{A}}(k)}{k}\xrightarrow{a.s.}\langle
t_{\mathfrak{A}}\rangle:=\left\langle\varphi,-\frac{{\bf
1}}{\mathbf{L}_{\infty}}\underline{1}\right\rangle.$ (12)

Lemma 1 below ensures that the expressions appearing in (7), (9) and (10) are
well defined and that the identities are true. Before stating the lemma, we
need to recall a few notions that will also be useful in the rest of the
paper. Given a matrix $\mathbf{A}\in M_{n}(\mathbb{C})$, the spectral radius
of $\mathbf{A}$ is defined as

$r(\mathbf{A}):=\max\\{|z|:\,z\in{\rm Sp}(\mathbf{A})\\}.$

The spectral radius is fundamental in studying the convergence of the
geometric series $\sum_{k\geq 0}\mathbf{A}^{k}$, since Gelfand formula states
that

$\lim_{k\rightarrow+\infty}\|\mathbf{A}^{k}\|^{\frac{1}{k}}=r(\mathbf{A}).$

Therefore, if $r(\mathbf{A})<1$, the series converges.

######  Lemma 1.

The following statements hold true:

  1. 1.

$\overline{\lambda}:=-\max\\{\Re(z):z\in{\rm Sp}(\mathbf{L}_{\infty})\\}>0$,
hence $\mathbf{L}_{\infty}$ is invertible;

  2. 2.

$r(\mathbf{R}^{-1}\mathbf{W}_{2})<1,$ therefore $\sum_{k\geq 0}\mathbf{S}^{k}$
is well defined with $\mathbf{S}=\mathbf{R}^{-1}\mathbf{W}_{2}$ and one has

$-\frac{{\bf 1}}{\mathbf{L}_{\infty}}=\sum_{k\geq 0}\left(\frac{{\bf
1}}{\mathbf{R}}\mathbf{W}_{2}\right)^{k}\frac{{\bf 1}}{\mathbf{R}},$

  3. 3.

for every $u<\overline{\lambda}$, one has

$\mathbb{E}_{\nu}[e^{uT_{\mathfrak{A}}(k)}]=\left\langle\nu,\left(\frac{\mathbf{L}_{\infty}}{u+\mathbf{L}_{\infty}}\mathbf{Q}\right)^{k}\underline{1}\right\rangle,$

  4. 4.

$\left\|\mathbf{L}_{\infty}^{-1}\right\|^{-1}_{\infty\rightarrow\infty}\leq\overline{\lambda}$.

The proof of Lemma 1 can be found in Appendix A.1. Loosely speaking, items 1
and 2 hold true because $\mathbf{L}_{\infty}$ and
$\mathbf{R}^{-1}\mathbf{W}_{2}$ are the counterparts of $\mathbf{R}$ and
$\mathbf{P}$, respectively, obtained by considering a restricted set of jumps
in the original irreducible Markov process.

Finally, we introduce here some Hilbert space notions which will be needed in
formulating our results and will be used in their proofs. The space of complex
functions on $E$ can be turned into a Hilbert space $L^{2}_{\pi}(E)$ using the
inner product $\langle\cdot,\cdot\rangle_{\pi}$ with respect to the invariant
measure $\pi$ defined in equation (2)

$\langle f,g\rangle_{\pi}:=\sum_{x\in E}\pi(x)\bar{f}(x)g(x).$

We use the notation $\|f\|_{\pi}$ for the corresponding norm. The adjoint
$\mathbf{A}^{\dagger}$ of an operator $\mathbf{A}$ on $L^{2}_{\pi}(E)$ has
matrix elements

$\mathbf{A}^{\dagger}_{xy}:=\frac{\pi(y)}{\pi(x)}\mathbf{A}_{yx}.$

From this it follows that $\mathbf{P}^{\dagger}$ is a transition operator in
its own right. An important quantity in this work is the _absolute spectral
gap_ of $\mathbf{P}$, which we denote by $\varepsilon$ and is defined as the
spectral gap of $\mathbf{P}^{\dagger}\mathbf{P}$ (the multiplicative
symmetrisation of $\mathbf{P}$):

$\varepsilon:=1-\max\\{\|\mathbf{P}f\|_{\pi}:\,\langle\pi,f\rangle=0,\,\|f\|_{\pi}=1\\}.$
(13)

Using this we define the _León-Perron operator_ $\hat{\mathbf{P}}$ associated
to $\mathbf{P}$ as([49])

$\hat{\mathbf{P}}:=(1-\varepsilon){\bf 1}+\varepsilon\Pi,$ (14)

where $\Pi$ is the map $\Pi:f\mapsto\langle
f,\underline{1}\rangle_{\pi}\underline{1}$. $\hat{\mathbf{P}}$ is a self-
adjoint transition operator which is simple to handle and will allow us to
derive upper bounds for the fluctuations of FPTs of $\mathbf{P}$.

###  2.2 Results on Classical Markov processes

In this section we describe our results for classical Markov processes. We
then illustrate these results by considering three simple specific examples.

####  2.2.1 Large Deviation Principle for General Counting Observables

We recall that, given a function
$I_{\mathfrak{A}}:\mathbb{R}\rightarrow[0,+\infty]$, the stochastic process
$\\{T_{\mathfrak{A}}(k)/k\\}$ is said to satisfy a Large Deviation Principle
with rate function $I_{\mathfrak{A}}$ if for every Borel measurable set
$B\subseteq\mathbb{R}$ one has that [11, 12]

$\begin{split}&-\inf_{t\in\overset{\circ}{B}}I_{\mathfrak{A}}(t)\leq\liminf_{k\rightarrow+\infty}\frac{1}{k}\log\left(\mathbb{P}_{\nu}\left(\frac{T_{\mathfrak{A}}(k)}{k}\in
B\right)\right),\\\
&\limsup_{k\rightarrow+\infty}\frac{1}{k}\log\left(\mathbb{P}_{\nu}\left(\frac{T_{\mathfrak{A}}(k)}{k}\in
B\right)\right)\leq-\inf_{t\in\overline{B}}I_{\mathfrak{A}}(t),\end{split}$

where $\overset{\circ}{B}$ and $\overline{B}$ denote the interior and the
closure of $B$, respectively. The rate function $I_{\mathfrak{A}}(t)$ is
called good if it has compact level sets.

######  Theorem 2.

Let us consider any nonempty subset $\mathfrak{A}$ of the set of possible
jumps. The collection of corresponding FPTs $\\{T_{\mathfrak{A}}(k)/k\\}$
satisfies a LDP with good rate function given by

$I_{\mathfrak{A}}(t):=\sup_{u\in\mathbb{R}}\\{ut-\log(r(u))\\}$

where

$r(u)=\begin{cases}r\left(\mathbf{Q}_{u}\right)&\text{ if
}u<\overline{\lambda}\\\ +\infty&\text{otherwise}\end{cases}$

where $\mathbf{Q}_{u}:=-(u+\mathbf{L}_{\infty})^{-1}\mathbf{W}_{1}$ and
$\overline{\lambda}:=-\max\\{\Re(z):z\in{\rm Sp}(\mathbf{L}_{\infty})\\}.$

The proof of Theorem 2 can be found in Appendix A.2; the proof highlights some
properties of $r(u)$, which imply (as one would expect) that
$I_{\mathfrak{A}}(t)=+\infty$ for $t\leq 0$ and that

$\lim_{t\rightarrow
0^{+}}I_{\mathfrak{A}}(t)=+\infty,\quad\lim_{t\rightarrow+\infty}I_{\mathfrak{A}}(t)=+\infty,\quad\lim_{t\rightarrow+\infty}I_{\mathfrak{A}}^{\prime}(t)=\overline{\lambda}.$

Moreover, $I_{\mathfrak{A}}(t)$ has a unique minimum in $\langle
t_{\mathfrak{A}}\rangle$, where it is equal to $0$. The strong law of large
numbers is a consequence of the smoothness of $r(u)$ around $0$; see for
instance [50, Theorem II.6.3 and Theorem II.6.4]. We refer to [17, 21] for a
more in depth discussion of the physical meaning of this result.

####  2.2.2 Concentration Bound for Dynamical Activity

Recall that we consider a classical continuous time Markov process with
generator $\mathbf{L}$ whose jumps can be described by a discrete time process
with transition matrix $\mathbf{P}$, cf. Eq. (1). The dynamical activity
$K_{\mathfrak{E}}(t)$ is the total number of configuration changes (referred
to also as jumps) occurring in a trajectory up to time $t$ [7, 14, 9]. The
corresponding first passage time $T_{\mathfrak{E}}(k)$, is the time of the
$k$-th jump, cf. Eq. (3). The first result of this paper is an upper bound on
the probability that the average jump time $T_{\mathfrak{E}}(k)/k$ deviates
from its asymptotic or stationary mean:

$\langle t_{\mathfrak{E}}\rangle=\sum_{x\in E}\pi(x)\frac{1}{R_{x}}.$

We now introduce two quantities which appear in the bounds of Theorem 3 below:

  * 1.

the second moment at stationarity:

$2b_{c}^{2}:=\sum_{x\in E}\pi(x)\frac{2}{R^{2}_{x}};$ (15)

  * 2.

the longest expected waiting time:

$c_{c}:=\max_{x\in E}\left\\{\frac{1}{R_{x}}\right\\}=\frac{1}{R_{\rm min}}.$
(16)

######  Theorem 3 (Fluctuations of FPT for Activity).

Suppose Hypothesis 1 holds ($\mathbf{L}$ is irreducible) and let $\varepsilon$
be the spectral gap of $\mathbf{P}^{\dagger}\mathbf{P}$, cf. Eq. (13). For
every $\gamma>0$ the following holds true:

$\begin{split}&\mathbb{P}_{\nu}\left(\frac{T_{\mathfrak{E}}(k)}{k}\geq\langle
t_{\mathfrak{E}}\rangle+\gamma\right)\leq
C(\nu)\exp\left(-k\frac{\gamma^{2}\varepsilon}{4b_{c}^{2}}h\left(\frac{5c_{c}\gamma}{2b_{c}^{2}}\right)\right)\\\
{\rm and}\\\ &\mathbb{P}_{\nu}\left(\frac{T_{\mathfrak{E}}(k)}{k}\leq\langle
t_{\mathfrak{E}}\rangle-\gamma\right)\leq
C(\nu)\exp\left(-k\frac{\gamma^{2}\varepsilon}{4b_{c}^{2}}h\left(\frac{5c_{c}\gamma}{2b_{c}^{2}}\right)\right),\quad
k\in\mathbb{N},\end{split}$

where $h(x):=(\sqrt{1+x}+\frac{x}{2}+1)^{-1}$ and $C(\nu):=\max_{x\in
E}\left\\{\nu(x)/\pi(x)\right\\}$.

The proof of Theorem 3 can be found in Appendix A.3 and follows the same line
as in [51, Theorem 3.3]. From the proof, one can see that if $\mathbf{P}$ is
self-adjoint, one can derive an upper bound with a slightly different
expression which contains the spectral gap of $\mathbf{P}$ instead of its
absolute spectral gap.

Let us make few considerations regarding the quantities appearing in the
bound. $C(\nu)$ accounts for the difference between the initial measure and
the stationary one, in particular $C(\pi)=1$. The absolute spectral gap
$\varepsilon$ controls the speed at which an arbitrary density $\nu$ converges
to the invariant measure $\pi$ under iterations of the transition operator
$\mathbf{P}_{*}$: indeed, for every $k\geq 1$

$\|\mathbf{P}_{*}^{k}(\nu-\pi)\|_{1}\leq\left\|\mathbf{P}^{\dagger
k}\left(\frac{\nu^{1/2}}{\pi^{1/2}}-\underline{1}\right)\right\|_{\pi}\leq
2\varepsilon^{\frac{k}{2}}\left(1-\sum_{x\in
E}\nu(x)^{1/2}\pi(x)^{1/2}\right).$

This enables one to upper bound the deviation probability of
$T_{\mathfrak{E}}(k)$ using stationary properties of the system. We remark
that the use of the spectral gap of $\mathbf{P}^{\dagger}\mathbf{P}$ instead
of the one of $\mathbf{P}$ allows to bound the fluctuations of the first
passage time for every $k\geq 1$ and not only asymptotically in $k$. Small
values of $\varepsilon$ can correspond in some models to big fluctuations of
the first passage time (cf. Ref. [43] and example 2.3.2 below).

The quantity $b_{c}^{2}$ encodes the variance of $T_{\mathfrak{E}}(k)$ in the
stationary regime. Indeed, the distribution of the interarrival times $t_{i}$
at stationarity is the same as the random variable obtained drawing a state
$x$ from the invariant distribution $\pi$ and then sampling from an
independent exponential random variable with parameter $R_{x}$. Such a random
variable has a variance equal to

$2\sum_{x\in E}\pi(x)\frac{1}{R_{x}^{2}}-\left(\sum_{x\in
E}\pi(x)\frac{1}{R_{x}}\right)^{2}.$

Notice that the following inequalities hold true:

$b_{c}^{2}\leq 2\sum_{x\in E}\pi(x)\frac{1}{R_{x}^{2}}-\left(\sum_{x\in
E}\pi(x)\frac{1}{R_{x}}\right)^{2}\leq 2b_{c}^{2},$

hence the variance of the interrarival times at stationarity and $b_{c}^{2}$
(see Eq. (15)) differ at most by a factor $2$. The bigger $b_{c}^{2}$, the
bigger the fluctuations of the first passage time. Finally, as one might
reasonably expect, the dependence of the bound on $c_{c}$ is such that the
bigger $c_{c}$, the heavier the right tail. Notice that the ratio between
$b_{c}^{2}$ and $c_{c}$ that appears in the bound can be controlled by the
average at stationarity:

$\frac{R_{\rm min}}{R_{\max}}\langle
t_{\mathfrak{E}}\rangle\leq\frac{b_{c}^{2}}{c_{c}}=\sum_{x\in
E}\pi(x)\frac{R_{\rm min}}{R_{x}^{2}}\leq\langle t_{\mathfrak{E}}\rangle.$

On the other hand, $\varepsilon$ and $b_{c}^{2}$ are quite independent from
each other. For example, if one modifies uniformly the speed of the Markov
process $X$, i.e. $\mathbf{L}\rightarrow\lambda\mathbf{L}$ for some positive
$\lambda$, one has that the jump process does not change and therefore
$\varepsilon$ remains the same, while
$b_{c}^{2}\rightarrow\lambda^{-2}b_{c}^{2}$. Notice that the bound has the
right scaling with respect to this group of transformations: indeed, the bound
becomes

$C(\nu)\exp\left(-k\frac{(\lambda\gamma)^{2}\varepsilon}{4b_{c}^{2}}h\left(\frac{5c_{c}\lambda\gamma}{2b_{c}^{2}}\right)\right),$

which corresponds to the upper bound for deviations of the order
$\lambda\gamma$ for the original dynamics.

As a consequence of the proof of Theorem 3, we obtain an upper bound on the
variance at stationarity of the FPT corresponding to the dynamical activity.
This result complements the lower bound (or thermodynamic uncertainty
relation) for the FPT of the activity obtained in [21]:

######  Corollary 4.

The variance of the first passage time for the total activity at stationarity
is bounded from above by:

$\frac{{\rm
var}_{\pi}(T_{\mathfrak{E}}(k))}{k}\leq\left(1+\frac{2}{\varepsilon}\right)b_{c}^{2}.$

The proof of Corollary 4 can be found in Appendix A.3.

####  2.2.3 Tail Bound for General Counting Observables

Our second main result is a concentration bound on the tails of the
distribution of the FPT for general counting observables,
$T_{\mathfrak{A}}(k)/k$. Similarly to the above result, this bounds the
probability that $T_{\mathfrak{A}}(k)/k$ deviates from $\langle
t_{\mathfrak{A}}\rangle$. Recall that $\mathbf{L}_{\infty}$ is a sub-Markov
generator describing the jumps in $\mathfrak{A}^{C}$, cf. Eq. (6). We
introduce the following notation

$\beta:=\left\|\frac{{\bf
1}}{\mathbf{L}_{\infty}}\right\|_{\infty\rightarrow\infty}.$

In the case of the dynamical activity it is simply given by
$\beta=\max_{x}1/R_{x}$. In general, $\beta$ satisfies $\beta\geq\langle
t_{\mathfrak{A}}\rangle$ by equation (12), and as we show below, it can be
interpreted as the longest timescale of the system. Indeed, since
$-\mathbf{L}^{-1}_{\infty}$ is a positivity preserving map, one has that

$\|\mathbf{L}_{\infty}^{-1}\|_{\infty\rightarrow\infty}=\|\mathbf{L}_{\infty}^{-1}\underline{1}\|_{\infty}=\max_{x\in
E}\sum_{y\in E}|L_{\infty,xy}^{-1}|,$

and since

$\|\mathbf{L}_{\infty}^{-1}\underline{1}\|_{\infty}=\max_{\nu}-\langle\nu,\mathbf{L}_{\infty}^{-1}\underline{1}\rangle=\max_{\nu}\mathbb{E}_{\nu}[T_{\mathfrak{A}}(1)],$

we obtain

$\beta=\max_{\nu}\mathbb{E}_{\nu}[T_{\mathfrak{A}}(1)],$

where $\nu$ is a probability density on the state space. We can now state our
second main result:

######  Theorem 5 (Rare Fluctuations of General Counting Observable FPTs).

Let $\mathbf{L}$ be irreducible and $\mathfrak{A}\subseteq\mathfrak{E}$ be
nonempty. For every $k\in\mathbb{N}$ and $\gamma>\beta-\langle
t_{\mathfrak{A}}\rangle$

$\mathbb{P}_{\nu}\left(\frac{T_{\mathfrak{A}}(k)}{k}\geq\langle
t_{\mathfrak{A}}\rangle+\gamma\right)\leq\exp\left(-k\left(\frac{\gamma+\langle
t_{\mathfrak{A}}\rangle-\beta}{\beta}-\log\left(\frac{\gamma+\langle
t_{\mathfrak{A}}\rangle}{\beta}\right)\right)\right).$

The proof of the Theorem 5 can be found in Appendix B.

Here we comment briefly on the rather simple idea behind it. Let $Z$ be the
sum of $k$ independent exponential random variables with parameter
$\beta^{-1}$, then by applying the Chernoff bound one obtains that for every
$0\leq u<\beta^{-1}$

$\mathbb{P}(Z/k\geq\beta+\gamma^{\prime})\leq\exp\left(-k\left(u(\beta+\gamma^{\prime})+\log(\beta)+\log(\beta^{-1}-u)\right)\right).$

Optimising in $u$ in the previous equation, one gets

$\mathbb{P}(Z/k\geq\beta+\gamma^{\prime})\leq\exp\left(-k\left(\gamma^{\prime}\beta^{-1}-\log(1+\gamma^{\prime}\beta^{-1})\right)\right).$
(17)

As the interarrival times are distributed according to the matrix-exponential
distribution ([52]) with rate matrix $-\mathbf{L}_{\infty}$, and
$\beta=\|\mathbf{L}^{-1}_{\infty*}\|_{1\rightarrow 1}$, the moment generating
function of $T_{\mathfrak{A}}(k)$ is bounded from above by that of $Z$.
Equation (17) then provides the bound in Theorem 5.

Unlike the case of Theorem 3, the bound in Theorem 5 does not cover small
fluctuations and this makes it impossible to use to derive any bound on the
variance of $T_{\mathfrak{A}}(k)$ in the spirit of Corollary 4. Nevertheless,
using the explicit expression of the variance (see Lemma 17), one can derive
the following bound.

######  Corollary 6.

Given any non-empty set of jumps $\mathfrak{A}$, the variance of the
corresponding first passage time at stationarity is bounded from above by:

$\frac{{\rm
var}_{\varphi}(T_{\mathfrak{A}}(k))}{k}\leq\left(1+\frac{2}{\tilde{\varepsilon}}\right)\beta^{2},$

where

$\tilde{\varepsilon}:=1-\max\\{\|\mathbf{Q}f\|_{\infty}:\|f\|_{\infty}=1,\,\langle\varphi,f\rangle=0\\}.$

The proof of Corollary 6 can be found in Appendix B. We recall that $\varphi$
is the unique invariant law for ${\bf Q}$ and was defined in Equation (11). We
remark that Corollary 6 together with Chebyschev inequality provides bounds on
small deviations as well.

The constant $\beta$ may be difficult to compute, especially for large
systems. However, it is not hard to check that Theorem 5 keeps holding true if
we replace $\beta$ with any $\tilde{\beta}\geq\beta$. The corollary that
follows shows that it is possible to upper bound $\beta$ (and obtain
alternative concentration bounds for the FPT) in terms of the following
simpler quantities of the system:

  * 1.

maximum escape rate:

$R_{\rm max}:=\max_{x\in E}\\{R_{x}\\};$ (18)

  * 2.

minimum transition rate:

$w_{\rm min}:=\min_{x,y\in E}\\{w_{xy}:w_{xy}>0\\};$ (19)

  * 3.

minimax jump distance $\tilde{k}$: the minimum $k\in\mathbb{N}$ such that for
any initial state $i\in E$ there exists a trajectory
$(i_{0}=i,i_{1},\dots,i_{l})$ with $l\leq k$ such that $w_{i_{j},i_{j+1}}>0$
for all $j=0,\dots l-1$ and the trajectory ends with a jump in $\mathfrak{A}$,
i.e. $(i_{l-1},i_{l})\in\mathfrak{A}$.

Figure 1: Minimax Jump Distance. Configurations of a discrete system are
represented by circles, and allowed transitions between them by arrows. Jumps
in $\mathfrak{A}$ (full/red) contribute to the observable, whilst jumps in
$\mathfrak{A}^{C}$ (dotted/blue) do not. (a) System where red jumps are
distributed throughout the graph, in this case $\tilde{k}=1$. (b) Uneven
distribution of jumps in $\mathfrak{A}$, in this case $\tilde{k}=4$.

While $R_{\rm max}$ and $w_{\rm min}$ can be computed easily in terms of the
transition rates, the minimax jump distance $\tilde{k}$ can be read off the
graph of the process, see Figure 1. The fact that it is finite follows from
the irreducibility of the Markov process. The corollary is stated below:

######  Corollary 7 (Simple Upper Bound on $\beta$).

For general counting observables, the norm
$\beta:=\left\|\mathbf{L}_{\infty}^{-1}\right\|_{\infty\rightarrow\infty}$ is
bounded from above by:

$\beta\leq
c_{c}\tilde{k}\max_{(x,y)\notin\mathfrak{A}}\left\\{\frac{R_{x}}{w_{xy}}\right\\}^{\tilde{k}-1}\max_{(x,y)\in\mathfrak{A}}\left\\{\frac{R_{x}}{w_{xy}}\right\\}\leq
c_{c}\tilde{k}\left(\frac{R_{\rm max}}{w_{\rm
min}}\right)^{\tilde{k}}=:\tilde{\beta},$

with $c_{c},R_{\rm max},w_{\rm min}$ defined in Eqs. (16), (18), and
respectively (19). The concentration bound in Theorem 5 holds with $\beta$
replaced by any of the two upper bounds above.

The proof of Corollary 7 can be found in Appendix B. In the case of total
activity, i.e. when $\mathfrak{A}=\mathfrak{E}$, one can easily see that
$\beta=c_{c}$.

###  2.3 Examples: Classical Concentration Bounds for Markov Processes

In this section we illustrate the main results of the classical part of the
paper with three simple examples.

####  2.3.1 Statistics of Dynamical Activity in a Three-Level System

We illustrate the results of Theorem 3 with the model of a simple three-level
system as sketched in Fig. 2(a): the set of configurations is $E=\\{0,1,2\\}$,
with reversible transitions $w_{01}=w_{10}=\omega$, $w_{02}=w_{20}=\upsilon$
and $w_{12}=w_{21}=\kappa$. Assuming that $\omega$ is the largest rate, the
longest expected waiting time is $c_{c}=\frac{1}{\kappa+\upsilon}$, whilst
$\langle t_{\mathfrak{E}}\rangle$, $b_{c}^{2}$ and $\varepsilon$ can easily be
determined from the three-dimensional generator $\mathbf{L}$. In addition, we
have $\beta=c_{c}$, for $\mathfrak{A}=\mathfrak{E}$. In Fig. 2(b) we show the
exact long time rate function of the activity (full curve/black) for a
particular set of values of the transitions rates, together with the lower
bound from Theorem 3 (dashed/blue),

$\tilde{I}_{\mathfrak{E}}(\gamma)=\frac{\gamma^{2}\varepsilon}{4b_{c}^{2}}h\left(\frac{5c_{c}\gamma}{2b_{c}^{2}}\right),$

and the general lower bound from Theorem 5 (dotted/red),

$\hat{I}_{\mathfrak{E}}(\gamma)=\frac{\gamma+\langle
t_{\mathfrak{E}}\rangle}{c_{c}}-1-\log\left(\frac{\gamma+\langle
t_{\mathfrak{E}}\rangle}{c_{c}}\right).$

We see that the bound from Theorem 5 $\hat{I}_{\mathfrak{E}}(\gamma)$ is
closer to the exact result than that from Theorem 3 for large enough
deviations. Indeed, for $\gamma\gg 1$, one has
$\hat{I}_{\mathfrak{E}}(\gamma)\asymp\frac{\gamma}{c_{c}}$ while
$\tilde{I}_{\mathfrak{E}}(\gamma)\asymp\frac{\gamma\varepsilon}{5c_{c}}<\frac{\gamma}{c_{c}}$.
For comparison, Fig. 2(b) we also show the upper bound to the rate function,
the so-called TUR, from [21] (dot-dashed/magenta): the combination of the TUR
and the “inverse TUR” from Theorems 3,5 upper and lower bound the true rate
function thus restricting the range of probabilities of rare events of the
activity.

Figure 2:  Bounds on the rate function of the FPT of the activity in a
classical three-level system. (a) Sketch of the three-level system. (b) Rate
function $I(T_{\mathfrak{E}}(k)/k)$ of the FPT for the dynamical activity, for
the case with rates $w_{01}=w_{10}=\omega=1$, $w_{02}=w_{20}=\upsilon=0.5$,
$w_{12}=w_{21}=\kappa=0.2$. We show the exact rate function (full curve/black)
and the lower bound specific to the activity from Theorem 3 (dashed/blue). We
also show the the generic tail bound for counting observables from Theorem 5
(dotted/red) which is valid in the region
$T_{\mathfrak{E}}(k)/k>\tilde{\beta}=1/R_{\rm min}=1/(\kappa+\upsilon)$
(indicated by the arrow). For comparison we include the upper bound on the
rate function (dot-dashed/magenta), known as the TUR [21].  Figure 3: Six-
state dynamical system. Sketch of a six-state system with two phases, the
active phase $E_{1}$ in the left circle and the inactive phase $E_{2}$ in the
right circle. The phases are separated by edges controlled by $\omega$. For
small $\omega$, each phase is metastable, and for $\omega\rightarrow 0$ the
size of FPT fluctuations increases. This increase is captured by
$\varepsilon$.

####  2.3.2 Metastability and the Absolute Spectral Gap

In the following example we show how closing the absolute spectral gap of the
discrete time generator ${\bf P}$ leads to an increase of the fluctuations of
the total activity FPT in a simple model, as predicted by the concentration
bound in Theorem 3. We consider the six-state system introduced in [43]
composed of two three-state subsystems connected by edges controlled by a rate
parameter $\omega$, see Fig. 3. For $\omega\rightarrow 0$ the spectral gap of
the real part of the generator $\Re(\mathbf{L})$ vanishes and the
configuration space $E$ breaks up into two disconnected components,
$E_{1}=\\{1,2,3\\}$ and $E_{2}=\\{4,5,6\\}$. When $\omega$ is non-zero but
much smaller than the other rates, the system is metastable, with $E_{1}$ and
$E_{2}$ becoming long-lived metastable “phases”, since relaxation within
$E_{1,2}$ will be much faster than relaxation in the whole of $E$.

We now study the statistics of the FPT of the activity in this model. We
consider the case where the internal rates in $E_{1}$ are much larger than
those in $E_{2}$, while maintaining the metastability condition,
$\lambda_{1},\kappa_{1}\gg\lambda_{2},\kappa_{2}\gg\omega$. We call $E_{1}$
and $E_{2}$ the “active phase” and “inactive phase”, respectively, as the
activity in stationary trajectories is much larger while the system is in
$E_{1}$ than in $E_{2}$. The rate matrix can be written as,

$\mathbf{W}=\begin{pmatrix}\tilde{\mathbf{W}}_{1}&0\\\
0&\tilde{\mathbf{W}}_{2}\end{pmatrix}+\omega\begin{pmatrix}0&{\bf 1}_{3}\\\
{\bf 1}_{3}&0\end{pmatrix},$

where $\tilde{\mathbf{W}}_{1,2}$ are the $3\times 3$ rate matrices for
internal transitions in $E_{1,2}=\\{1,2,3\\}$, and the 3-dimensional identity
is denoted ${\bf 1}_{3}$. In Theorem 3 we require the discrete time operator
$\mathbf{P}=\mathbf{R}^{-1}\mathbf{W}$ and its adjoint $\mathbf{P}^{\dagger}$,
to form the multiplicative symmertisation

$\mathbf{P}^{\dagger}\mathbf{P}=\begin{pmatrix}\frac{\tilde{\mathbf{W}_{1}}^{\dagger}\tilde{\mathbf{W}_{1}}}{R_{1}^{2}}&0\\\
0&\frac{\tilde{\mathbf{W}_{2}}^{\dagger}\tilde{\mathbf{W}_{2}}}{R_{2}^{2}}\end{pmatrix}+\omega^{2}\begin{pmatrix}\frac{1}{R_{2}^{2}}{\bf
1}_{3}&0\\\ 0&\frac{1}{R_{1}^{2}}{\bf
1}_{3}\end{pmatrix}+\omega\begin{pmatrix}0&\frac{\tilde{\mathbf{W}}_{1}^{\dagger}}{R_{1}^{2}}+\frac{\tilde{\mathbf{W}}_{2}}{R_{2}^{2}}\\\
\frac{\tilde{\mathbf{W}}_{2}^{\dagger}}{R_{2}^{2}}+\frac{\tilde{\mathbf{W}}_{1}}{R_{1}^{2}}&0\end{pmatrix},$

where $R_{1,2}=\lambda_{1,2}+\kappa_{1,2}$. At $\omega=0$, the spectrum of
$\mathbf{P}^{\dagger}\mathbf{P}$ is equal to the union of the spectra of
$\tilde{\mathbf{P}}_{1}^{\dagger}\tilde{\mathbf{P}}_{1}$ and
$\tilde{\mathbf{P}}_{2}^{\dagger}\tilde{\mathbf{P}}_{2}$, where
$\tilde{\mathbf{P}}_{1}=\frac{\tilde{\mathbf{W}}_{1}}{R_{1}}$ is the discrete
time transition matrix on each $E_{1}$ and $\tilde{\mathbf{P}}_{2}$ is that of
$E_{2}$; hence, the algebraic multiplicity of the eigenvalue $1$ is $2$. By
continuity of the spectrum for analytic perturbation, the absolute spectral
gap vanishes as $\omega\rightarrow 0$. Corollary 4 then implies that the upper
bound on the variance of the FPT will explode as this “phase transition” point
is approached. Fluctuations of $T_{\mathfrak{E}}(k)$’s get bigger as well:
since $\omega$ is much less than either of the escape rates within each
metastable phase, the system gets “stuck” in either phase, resulting in larger
fluctuations of the observed FPT.

The behaviour of the fluctuations of $T_{\mathfrak{E}}(k)$ as $\omega\to 0$ is
not immediately apparent based on the form of the expression for the variance
given by Lemma 17. We remark that for finite $k$ the variance remains finite
even as the gap closes. This can be seen by rewriting ${\rm
var}_{\pi}(T_{\mathfrak{E}}(k))$ as

$\begin{split}\frac{{\rm
var}_{\pi}\left(T_{\mathfrak{E}}(k)\right)}{k}=\left\langle\pi,\mathbf{D}\underline{1}\right\rangle^{2}&+2\left\langle\pi,\mathbf{D}\left({\bf
1}+\frac{\sum_{i=1}^{k-1}\sum_{j=1}^{i}\mathbf{P}^{j}}{k}\right)({\bf
1}-\Pi)\mathbf{D}\underline{1}\right\rangle\\\ \end{split}$

which is uniformly bounded in $\omega$. Recall that in the case of total
activity $\varphi=\pi$,
$\mathbf{L}_{\infty}^{-1}=-\mathbf{R}^{-1}=-\mathbf{D}$ and
$\mathbf{Q}=\mathbf{P}$. In the limit $k\to\infty$ the expression reduces to
the first two terms of Lemma 17 and the behaviour depends solely on $({\bf
1}-\mathbf{P})^{-1}$ and whether this causes a divergence as $\omega\to 0$.
From Figure 4 one can see that for this model, the asymptotic variance does
diverge and for finite $k$ the fluctuations remain finite as expected. We can
however see fingerprints of the asymptotic behaviour for intermediate $k$,
which is captured by the upper bound in Corollary 4.

Figure 4: Upper bound on the variance of the FPT for activity in a six-state
system. Upper bound (full/black) on the scaled variance of ${\rm
var}_{\pi}(T_{\mathfrak{E}}(k))/k$ given by Corollary 4. This is valid for all
$k$. We compare with the exact variance (cf Lemma 17) for several values of
$k$: $1$ (dashed-marked/blue), $10^{1}$ (dotted-marked/orange), $10^{2}$
(dotted/yellow), $10^{3}$ (dot-dashed/purple) and for $k=\infty$
(dashed/magenta). We compare these quantities as the controlling parameter
$\omega\to 0$ and the system approaches a phase transition. The system is the
model given in figure 3 with rates $\lambda_{1}=30$, $\mu_{1}=10$ and
$\lambda_{2}=0.3$, $\mu_{2}=0.1$. Figure 5: Bounds on the rate function of the
FPT of a counting observable for a classical three-level system. Exact rate
function $I(T_{\mathfrak{A}}(k)/k)$ (full/black) for the FPT of the total
count of jumps $0\rightarrow 1$, $1\rightarrow 2$ and $2\rightarrow 0$ in the
three-level system of Fig. 2, with rates $w_{01}=w_{10}=\omega=1$,
$w_{02}=w_{20}=\upsilon=0.9$, $w_{12}=w_{21}=\kappa=0.8$. The tail bound from
Theorem 5 (dotted/red) bounds deviations in the region
$T_{\mathfrak{A}}(k)/k>\tilde{\beta}$ with
$\beta\leq\tilde{\beta}={(\omega+\upsilon)}/{[\kappa(\kappa+\upsilon)]}$. The
rate function is bounded from above using the same method as in Fig. 2(dot-
dashed/magenta) [21].

####  2.3.3 Three-Level System Counting Subset of Jumps

To illustrate the results of Theorem 5, we use the same three-level model as
in Sec. 2.3.1 but we consider the observable that only counts “clockwise”
jumps, that is, the $0\rightarrow 1$, $1\rightarrow 2$ and $2\rightarrow 0$
jumps but not their reverses. With this setup, the minimax jump distance is
$\tilde{k}=1$ since it is possible to perform a jump in $\mathfrak{A}$ which
begins at any state. The lower bound to the rate function provided by Theorem
5 is illustrated in Figure 5.

##  3 Large Deviation Principle and Concentration Bounds for FPTs of Quantum
Counting Processes

In this section we present three concentration bounds for _quantum_ Markov
processes. First we provide a result for _total counts_ in quantum Markov
processes with general jump operators. By restricting to _reset processes_
(jump operators of rank one), we can weaken the required assumption and obtain
a separate result. Finally, we provide a bound for counting a _subset_ of
jumps. In each of the three cases we illustrate the result in a simple
example.

###  3.1 Preliminaries and Notation

In this section we introduce the basic concepts and tools related to first
passage times for quantum counting processes. We recall that quantum counting
processes are used to model detector clicks when an open quantum system is
continuously monitored through the environment [3]. Throughout the paper, the
system will be finite dimensional and its state space will be the Hilbert
space $\mathbb{C}^{d}$. Quantum states are represented by positive semi-
definite matrices with unit trace, that is $\rho\in M_{d}(\mathbb{C})$ such
that $\rho\geq 0$ and ${\rm tr}(\rho)=1$. Observables correspond to self
adjoint operators on the state space, i.e. $x\in M_{d}(\mathbb{C})$ such that
$x=x^{*}$. As in the classical case, there is a duality between states and
observables expressed by the fact that the expectation of an obsevable $x$ in
the state $\rho$ is ${\rm tr}(\rho x)$. We can endow $M_{d}(\mathbb{C})$ with
the operator and trace norms which provide natural distances between
observables and states, respectively:

$\|x\|_{\infty}:=\max_{u\in\mathbb{C}^{d}\setminus\\{0\\}}\frac{\|xu\|}{\|u\|},\quad\|x\|_{1}:={\rm
tr}(|x|).$

For any linear map $\Phi$ on $M_{d}(\mathbb{C})$ describing the evolution of
observables (Heisenberg picture), the unique corresponding evolution
$\Phi_{*}$ on states (Schrödinger picture) is characterised by

${\rm tr}(x\Phi(y))={\rm tr}(\Phi_{*}(x)y).$

As in the previous section, we denote by $\|\Phi\|_{\infty\rightarrow\infty}$
the operator norm on $\Phi$ induced by $\|\cdot\|_{\infty}$ and analogously
for the trace norm. Every physical evolution of a quantum system is given by a
quantum channel, i.e. a linear map $\Phi:M_{d}(\mathbb{C})\rightarrow
M_{d}(\mathbb{C})$ which satisfies

  1. 1.

$\Phi({\bf 1})={\bf 1}$ (unital),

  2. 2.

$\Phi\otimes{\bf I}_{M_{k}(\mathbb{C})}$ is positive for every
$k\in\mathbb{N}$ (completely positive)

where ${\bf 1}$ is the identity matrix and ${\bf I}_{M_{k}(\mathbb{C})}$ is
the identity map on $M_{k}(\mathbb{C})$. Equivalently, $\Phi_{*}$ is trace
preserving and completely positive. These conditions mirror those satisfied by
classical channels/transition operators, but in the quantum setting complete
positivity is a stronger requirement that usual positivity, and we refer to
[53] for more details on the theory of quantum channels and the physical
interpretation.

####  3.1.1 Quantum Markov Semigroups and their Unraveling by Counting
Measurements

A quantum Markov semigroup is a family of channels
$\left(\mathcal{T}_{t}\right)_{t\geq 0}$ acting on $M_{d}(\mathbb{C})$ such
that $\mathcal{T}_{0}={\bf I}_{M_{d}(\mathbb{C})}$,
$\mathcal{T}_{t}\circ\mathcal{T}_{s}=\mathcal{T}_{t+s}$ for all $s,t\geq 0$
and $t\mapsto{\cal T}_{t}$ is continuous. Such a semigroup describes (in the
Heisenberg picture) the dissipative evolution of a $d$-dimensional open
quantum system, in physical situations where certain Markov approximations
pertaining to the interaction with the environment apply. A fundamental result
[54, 55] shows that the generator $\mathcal{L}:M_{d}(\mathbb{C})\to
M_{d}(\mathbb{C})$ of such a semigroup takes the form

$\mathcal{L}:x\mapsto-i[H,x]+\sum_{i\in
I}L_{i}^{*}xL_{i}--\frac{1}{2}\sum_{i\in I}(L_{i}^{*}L_{i}x+xL_{i}^{*}L_{i}),$
(20)

where $H\in M_{d}(\mathbb{C})$ is self-adjoint and $L_{i}\in
M_{d}(\mathbb{C})$ with indices beloging to a finite set $I$. Physically, $H$
is interpreted as being the system hamiltonian while $L_{i}$ describe the
coupling to separate “emission channels” in the environment. If the system is
prepared in a state $\rho$ and evolves together with the environment for a
time period $t$, then its reduced state is given by $\mathcal{T}_{t*}(\rho)$.
On the other hand, if the environment is probed by performing continuous-time
counting measurements in each of the emission channels, then one one observes
stochastic trajectories $\omega=\\{(i_{1},t_{1}),(i_{2},t_{2}),\cdots\\}$
which record the labels of the jumps together with the times between jumps. In
this case one would like to know what is the probability of observing such a
trajectory and what is the conditional state of the system given this
observation. This is the subject of quantum filtering theory which plays an
important role in quantum technology and quantum control theory [56, 57, 58,
59]. While a full account of the system-environment unitary evolution and
subsequent counting measurement goes beyond the scope of this paper, we employ
the Dyson series to convey an intuitive answer to the questions formulated
above. For this we decompose the generator as

$\mathcal{L}=\mathcal{L}_{0}+\mathcal{J}=\mathcal{L}_{0}+\sum_{i\in
I}\mathcal{J}_{i},$ (21)

where

$\mathcal{L}_{0}(x)=G^{*}x+xG\qquad\mathcal{J}_{i}(x)=L_{i}^{*}xL_{i},\quad\mathrm{with}\quad
G:=iH-\frac{1}{2}\sum_{i\in I}L_{i}^{*}L_{i}.$

Note that $\mathcal{J}_{i}$ is completely positive and $\mathcal{L}_{0}$ is
the generator of the completely positive semigroup
$e^{\mathcal{L}_{0}}(x)=e^{G^{*}t}xe^{Gt}$. The Dyson expansion of
$\mathcal{T}_{*t}$ (Schrödinger picture) corresponding to the split (21) is

$\mathcal{T}_{t*}=e^{t{\cal
L}_{0*}}+\sum_{k=1}^{+\infty}\int_{\sum_{i=1}^{k}t_{i}\leq
t}e^{\left(t-\sum_{i=1}^{k}t_{i}\right){\cal L}_{0*}}{\cal
J}_{i_{k}*}e^{t_{k}{\cal L}_{0*}}\cdots{\cal J}_{i_{1}*}e^{t_{1}{\cal
L}_{0*}}dt_{1}\cdots dt_{k}.$

By applying both sides to the initial state $\rho$ we find that the evolved
system state $\rho_{t}=\mathcal{T}_{*t}(\rho)$ is a mixture of states
corresponding to different counting trajectories. Indeed, let us denote

$\Omega_{t}=\\{\emptyset\\}\cup\bigcup_{k=1}^{+\infty}I^{k}\times\\{(t_{1},\dots,t_{k})\in[0,t]^{k}:\sum_{i=1}^{k}t_{i}\leq
t\\}$

the space of counting trajectories up to time $t$, and let us endow
$\Omega_{t}$ with the natural $\sigma$-field and denote by $d\mu$ the unique
measure such that $\mu(\\{\emptyset\\})=1$ and
$\mu(\\{(i_{1},\dots,i_{k})\times B)$ is the Lebesgue measure of $B$ for every
$(i_{1},\dots,i_{k})\in I^{k}$,
$B\subseteq\\{(t_{1},\dots,t_{k})\in[0,t]^{k}:\sum_{i=1}^{k}t_{i}\leq t\\}$.
Then we can write

$\mathcal{T}_{t*}(\rho)=\int_{\Omega_{t}}\tilde{\varrho}_{t}(\omega)\mu(d\omega)=\int_{\Omega_{t}}\frac{d\mathbb{P}_{t}}{d\mu}(\omega)\varrho_{t}(\omega)\mu(d\omega)$

where for each counting trajectory
$\omega=\\{(i_{1},t_{1}),\dots(i_{k},t_{k})\\}\in\Omega_{t}$. The
_unnormalised_ system state conditional on observing $\omega$ is given by

$\tilde{\varrho}_{t}(\omega)=e^{\left(t-\sum_{i=1}^{k}t_{i}\right){\cal
L}_{0*}}{\cal J}_{i_{k}*}e^{t_{1}{\cal L}_{0*}}\cdots{\cal
J}_{i_{1}*}e^{t_{1}{\cal L}_{0*}}(\rho)$ (22)

while

$\frac{d\mathbb{P}_{t}}{d\mu}(\omega)={\rm
tr}(\tilde{\varrho}_{t}(\omega)),\quad\varrho_{t}(\omega)=\frac{\tilde{\varrho}_{t}(\omega)}{{\rm
tr}(\tilde{\varrho}_{t}(\omega))}$ (23)

represent the probability density, and the _normalised_ conditional state,
respectively.

With this interpretation, the Dyson expansion expresses the fact that by
averaging over all the conditional states $\varrho_{t}(\omega)$ one obtains
the reduced system state $\rho_{t}$. Note that in order to avoid confusion, we
use different symbols for the conditional and reduced system states.

Based on equations (22) and (23) we deduce that during time periods with no
jumps the conditional state evolves continuously as

$\varrho_{t}\mapsto\varrho_{t+s}:=\frac{e^{s\mathcal{L}_{0*}}(\varrho_{t})}{{\rm
tr}[e^{s\mathcal{L}_{0*}}(\varrho_{t})]},$

and at the time of a count with index $i$ the state has an instantaneous jump

$\varrho_{t}\mapsto\frac{\mathcal{J}_{i*}(\varrho_{t})}{{\rm
tr}[\mathcal{J}_{i*}(\varrho_{t})]}.$

In addition, the probability density for the time of the first jump after $t$
is

$w(s)={\rm tr}[\mathcal{J}_{*}e^{s\mathcal{L}_{0*}}(\varrho_{t})]=-{\rm
tr}[\mathcal{L}_{0*}e^{s\mathcal{L}_{0*}}(\varrho_{t})]$

where we use the fact that
$\mathcal{J}(\mathbf{1})+\mathcal{L}_{0}(\mathbf{1})=\mathcal{L}(\mathbf{1})=0$.
We will now show how to generate the count trajectories in a recursive manner
which is reminiscent of the generation of trajectories of classical Markov
processes. Given a trajectory
$\omega=\\{(i_{1},t_{1}),(i_{2},t_{2}),\dots\\}$, we denote by $\varrho_{k}$
the state immediately after the $k^{\rm th}$ count, with $\varrho_{0}=\rho$
denoting the initial state.

Iterative procedure for generating quantum trajectories. The interarrival
times and quantum trajectories can be generated recursively with respect to
$k=0,1,\dots$: given $\varrho_{k}$ we draw $(\varrho_{k+1},i_{k+1},t_{k+1})$
as follows:

  1. 1.

the $(k+1)$th interrarival time $t_{k+1}$ is drawn from the density

$w(t)=-{\rm tr}(\mathcal{L}_{0*}e^{t\mathcal{L}_{0*}}(\varrho_{k}))$

  2. 2.

given $t_{k+1}$, the label $i_{k+1}$ is sampled from the following
distribution:

$p(j)=\frac{{\rm
tr}(\Phi_{j*}\mathcal{L}_{0*}e^{t_{k+1}\mathcal{L}_{0*}}(\varrho_{k}))}{{\rm
tr}(\Phi_{*}\mathcal{L}_{0*}e^{t_{k+1}\mathcal{L}_{0*}}(\varrho_{k}))},\quad\Phi_{j}:=-\mathcal{L}_{0}^{-1}{\cal
J}_{j},\quad\Phi:=\sum_{j\in I}\Phi_{j}$

  3. 3.

we define

$\varrho_{k+1}=\frac{{\cal
J}_{i_{k+1}*}(e^{t_{k+1}\mathcal{L}_{0*}}(\varrho_{k}))}{{\rm tr}({\cal
J}_{i_{k+1}*}(e^{t_{k+1}\mathcal{L}_{0*}}(\varrho_{k})))}.$

The map $\Phi:=\sum_{j\in I}\Phi_{j}=-\mathcal{L}_{0}^{-1}{\cal J}$ appearing
in step 2. is the analogous of $\mathbf{P}$ in Section 2.1 and will play a
central role in the following. Lemma 9 shows that $\mathcal{L}_{0}^{-1}$ is
well defined and is equal to $-\int_{0}^{+\infty}e^{t\mathcal{L}_{0}}dt$,
hence $\Phi$ is a completely positive map. Moreover, using that
$\mathcal{L}({\bf 1})=0$, one has

$\Phi({\bf 1})=-\mathcal{L}_{0}^{-1}{\cal J}({\bf
1})=\mathcal{L}_{0}^{-1}\mathcal{L}_{0}({\bf 1})={\bf 1},$

hence $\Phi$ is a quantum channel.

As in the classical case, establishing results on law of large numbers, large
deviations, or concentration bounds, requires some type of assumption on the
ergodicity of the dynamics. We now introduce two irreducibility assumptions
which will later be invoked in separate occasions in our results.

######  Hypothesis 2 (Irreducibility of $\mathcal{L}$).

The generator $\mathcal{L}$ is irreducible. This means that there is no non-
trivial projection $P$ such that $\mathcal{L}(P)\geq 0$ or equivalently, there
exists a unique strictly positive state $\hat{\sigma}$ satisfying
$\mathcal{L}_{*}(\hat{\sigma})=0$.

######  Hypothesis 3 (Irreducibility of $\Phi$).

The channel $\Phi$ is irreducible. This means that there is no non-trivial
projection $P$ such that $\Phi(P)\geq P$ or equivalently, there exists a
unique strictly positive state $\sigma$ satisfying $\Phi_{*}(\sigma)=\sigma$.

As in the classical case, there is a close connection between the continuous-
time generator $\mathcal{L}$ and the channel $\Phi$. The following lemma
clarifies these connections and shows that Hypothesis 3 is strictly stronger
than Hypothesis 2.

######  Lemma 8.

The generator $\mathcal{L}$ has a unique invariant state if and only if $\Phi$
does. If $\Phi$ is irreducible then $\mathcal{L}$ is irreducible, but the
converse is generally not true.

The proof of Lemma 8 can be found in the appendix, section C.

####  3.1.2 First Passage Time for the Counting Process

Consider the counting process described in section 3.1.1 and let $N_{i}(t)$ be
the stochastic process given by the number of counts with label $i\in I$ up to
time $t$ in the measurement trajectory $\omega$. More generally, for any
subset $\mathfrak{A}\subseteq I$ we define the counting observable

$N_{\mathfrak{A}}(t)=\sum_{i\in\mathfrak{A}}N_{i}(t).$

When $\mathfrak{A}=I$, $N_{I}(t)$ is referred to as the total number of
counts. The corresponding first passage times (FPTs) are defined in the same
way as in the classical case:

$T_{\mathfrak{A}}(k):=\inf_{t\geq 0}\\{t:N_{\mathfrak{A}}(t)=k\\}.$ (24)

The following splitting of the generator is relevant in order to study the
properties of the stochastic process $T_{\mathfrak{A}}(k)$:

$\mathcal{L}=\mathcal{J}_{\mathfrak{A}}+\mathcal{L}_{\infty},$

where $\mathcal{J}_{\mathfrak{A}}(x)=\sum_{i\in\mathfrak{A}}L_{i}^{*}xL_{i}$
accounts for the change of state after a jump in $\mathfrak{A}$ and
$\mathcal{L}_{\infty}$ for the average evolution between jumps in
$\mathfrak{A}$. We denote as $\Psi$ the transition operator analogous to
$\mathbf{Q}$ in the classical case:

$\Psi(x)=-\mathcal{L}_{\infty}^{-1}\circ\mathcal{J}_{\mathfrak{A}}(x).$ (25)

If Hypothesis 2 holds, then $\Psi$ admits a unique invariant state $\varsigma$
(which might have a non-trivial kernel). Note that if $\mathfrak{A}=I$ then
$\mathcal{L}_{\infty}=\mathcal{L}_{0}$ and $\Psi=\Phi$.

The following lemma shows that all the objects introduced so far are well
defined and allows us to write the Laplace transform for general counting
observables.

######  Lemma 9.

Assume that Hypothesis 2 ($\mathcal{L}$ is irreducible) holds. Then the
following statements are true:

  1. 1.

$\overline{\lambda}:=-\max\\{\Re(z):z\in{\rm Sp}({\cal L}_{\infty})\\}>0$,
hence ${\cal L}_{\infty}$ is invertible;

  2. 2.

for every $u<\overline{\lambda}$, one has

$\mathbb{E}_{\rho}[e^{uT_{\mathfrak{A}}(k)}]={\rm
tr}\left(\rho\left((u+\mathcal{L}_{\infty})^{-1}\mathcal{L}_{\infty}\Psi\right)^{k}({\bf
1})\right),$

  3. 3.

$\|{\cal
L}_{\infty}^{-1}\|_{\infty\rightarrow\infty}^{-1}\leq\overline{\lambda}.$

The proof of Lemma 9 can be found in Appendix C. From the expression of the
moment generating function given in point 2 of the previous lemma, one can use
standard techniques to show that

$\frac{T_{\mathfrak{A}}(k)}{k}\xrightarrow{a.s.}\langle
t_{\mathfrak{A}}\rangle:=-{\rm
tr}\left(\varsigma\mathcal{L}_{\infty}^{-1}({\bf 1})\right)$ (26)

where $\varsigma$ is the unique invariant state of $\Psi$ defined in equation
(25). Our goal will be to investigate what is the probability of
$T_{\mathfrak{A}}(k)$ deviating from $\langle t_{\mathfrak{A}}\rangle$.

We introduce some more notation that will be useful in proving the
concentration bounds for the FPTs. We consider the Hilbert space structure of
$M_{d}(\mathbb{C})$ endowed with the following inner product:

$\langle x,y\rangle_{\sigma}:={\rm
tr}(\sigma^{\frac{1}{2}}x^{*}\sigma^{\frac{1}{2}}y),\quad x,y\in
M_{d}(\mathbb{C})$

and we denote it by $L^{2}(\sigma)$. Unlike the classical case, there are
infinitely many inner products induced by the stationary state $\sigma$ of
$\Phi$; the choice we adopt is known as Kubo-Martin-Schwinger (KMS) inner
product. The norm with respect to this inner product will be denoted by
$\|x\|_{\sigma}$. The KMS inner product allows us to define the trace of a map
$\mathcal{E}:M_{d}(\mathbb{C})\rightarrow M_{d}(\mathbb{C})$, by:

${\rm TR}(\mathcal{E})=\sum_{i=1}^{d^{2}}\langle
x_{i},\mathcal{E}(x_{i})\rangle_{\sigma},$

for an orthonormal basis $\\{x_{i}\\}$ of $M_{d}(\mathbb{C})$. The adjoint of
an operator $\mathcal{E}$ with respect to this inner product can be expressed
in terms of the predual map $\mathcal{E}_{*}$ as

$\mathcal{E}^{\dagger}(x)=\Gamma^{-\frac{1}{2}}\circ\mathcal{E}_{*}\circ\Gamma^{\frac{1}{2}}(x)$
(27)

where $\Gamma^{a}(x)=\sigma^{a}x\sigma^{a}$ for every $a\in\mathbb{R}$.

Given a quantum channel $\Phi$ with invariant state $\sigma$, its absolute
spectral gap $\varepsilon$ is defined as $1$ minus the square root of the
second largest eigenvalue of the multiplicative symmetrisation of $\Phi$,
namely $\Phi^{\dagger}\Phi$. As in the classical case, the proof of the
concentration bound in Theorem 11 will make use of the following León-Perron
operator corresponding to $\Phi$

$\hat{\Phi}=(1-\varepsilon){\bf I}_{M_{k}(\mathbb{C})}+\varepsilon\Pi,$

where ${\bf I}_{M_{k}(\mathbb{C})}$ is the identity map, and $\Pi$ is the map
$\Pi x\mapsto{\rm tr}(\sigma x){\bf 1}$ for $x\in M_{d}(\mathbb{C})$.
$\hat{\Phi}$ is a quantum channel with unique invariant state $\sigma$ and
which is self adjoint with respect to the KMS inner product induced by
$\sigma$.

###  3.2 Results on Quantum Markov Processes

We now present our three concentration bounds for quantum Markov processes,
two for the total counts process, followed by a bound on the right tail for
counts of a subset of jumps. We then illustrate the three results with simple
examples.

####  3.2.1 Large Deviation Principle for General Counting Observables

We start by obtaining a large deviation principle for quantum counting
processes, in analogy with what we did in Sec. 2.2.1.

######  Theorem 10.

Consider a nonempty subset $\mathfrak{A}$ of the emission channels. The FPT
$T_{\mathfrak{A}}(k)/k$ satisfies a large deviation principle with good rate
function given by

$I_{\mathfrak{A}}(t):=\sup_{u\in\mathbb{R}}\\{ut-\log(r(u))\\}$

where

$r(u)=\begin{cases}r\left(\Psi_{u}\right)&\text{ if }u<\overline{\lambda}\\\
+\infty&\text{o.w.}\end{cases}$

where
$\Psi_{u}(x):=-(u+\mathcal{L}_{\infty})^{-1}\mathcal{J}_{\mathfrak{A}}(x)$ and
$\overline{\lambda}:=-\max\\{\Re(z):z\in{\rm Sp}(\mathcal{L}_{\infty})\\}.$

The proof of Theorem 10 is in Appendix C.3.

####  3.2.2 Concentration Bound on Total Number of Counts

The first passage time for the total number of counts $T_{I}(k)$ is the time
it takes to observe $k$ counts of any kind on the system. Our first main
result for quantum Markov processes is a quantum version of Theorem 3 \- a
bound on the fluctuations of the FPT $T_{I}(k)$ for total jumps. We note that
in the quantum framework, “activity” is usually referred to as total “counts”
or “jumps” [60] (but other definitions exist [61]). From equation (26), the
asymptotic mean in this case is:

$\langle t_{I}\rangle:=-{\rm tr}(\sigma\mathcal{L}_{0}^{-1}({\bf 1})).$

We define

$c_{q}:=\|\mathcal{L}_{0}^{-1}\|_{\sigma\rightarrow\sigma}$ (28)

and note that this is the non-commutative counterpart of $c_{c}$, cf. (16).

######  Theorem 11 (Fluctuations of FPT for Total Counts ).

Assume that Hypothesis 3 holds ($\Phi$ be irreducible) and let $\varepsilon$
be the absolute spectral gap of $\Phi$. Then, for every $\gamma>0$:

$\begin{split}&\mathbb{P}_{\rho}\left(\frac{T_{I}(k)}{k}\geq\langle
t_{I}\rangle+\gamma\right)\leq
C(\rho)\exp\left(-k\frac{\gamma^{2}\varepsilon}{8c_{q}^{2}}h\left(\frac{5\gamma}{2c_{q}}\right)\right)\\\
{\rm and}\\\ &\mathbb{P}_{\rho}\left(\frac{T_{I}(k)}{k}\leq\langle
t_{I}\rangle-\gamma\right)\leq
C(\rho)\exp\left(-k\frac{\gamma^{2}\varepsilon}{8{c_{q}^{2}}}h\left(\frac{5\gamma}{2c_{q}}\right)\right),\quad
k\in\mathbb{N},\end{split}$

where $h(x):=(\sqrt{1+x}+\frac{x}{2}+1)^{-1}$,
$C(\rho):=\left\|\sigma^{-\frac{1}{2}}\rho\sigma^{-\frac{1}{2}}\right\|_{\sigma}$
and $c_{q}$ is defined in Eq. (28).

The proof of Theorem 11 can be found in Appendix C.4. As in the classical
case, the following corollary follows from the proof of Theorem 11.

######  Corollary 12.

The variance of the first passage time for total counts is bounded from above
by:

$\frac{{\rm
var}_{\sigma}(T_{I}(k))}{k}\leq\left(\frac{4}{\varepsilon}-(1-\varepsilon)\right)c_{q}^{2}.$

The proof of Corollary 12 can be found in Appendix C.4. Recall from section
3.1 that if Hypothesis 2 holds ($\mathcal{L}_{*}$ admits a unique and strictly
positive invariant state), then the uniqueness of the invariant state of
$\Phi_{*}$ is guaranteed, but not its strict positivity, hence the need for
Hypothesis 3. One can show however, that if Hypothesis 2 holds, then the
invariant state of $\Phi_{*}$ is strictly positive if and only if
$\cap_{i=1}^{|I|}\ker(L_{i}^{*})=\emptyset$.

####  3.2.3 Concentration Bound on Total Number of Counts for Reset Processes

In Theorem 11 we proved a concentration bound for the FPT corresponding to the
total number of counts, under the assumption that Hypothesis 3 holds. In this
subsection we consider _quantum reset processes_ which are characterised by
jump operators that have rank one, and we derive a FPT concentration bound
using the weaker Hypothesis 2.

Let us assume that the jump operators are of the form

$L_{i}=\ket{y_{i}}\bra{x_{i}}\quad
x_{i},y_{i}\in\mathbb{C}^{d}\setminus\\{0\\}.$ (29)

Without any loss of generality, we can assume that $\|y_{i}\|=1$. After
observing a click of the $i$-th detector, the state of the system is known and
is equal to $\ket{y_{i}}\bra{y_{i}}$. In this case, by applying step 2 of the
iterative procedure in section 3.1.1 we find that the sequence of click
indices is a classical Markov chain on $I$ with transition matrix
$\mathbf{P}:=(p_{ij})$

$p_{ij}=-\langle
x_{j}|\mathcal{L}_{0*}^{-1}(\ket{y_{i}}\bra{y_{i}})x_{j}\rangle.$ (30)

We remark that Hypothesis 2 is sufficient to imply the irreducibility of the
classical transition operator $\mathbf{P}$. Indeed since
$\mathcal{L}_{*}(\hat{\sigma})=0$ with stationary state $\hat{\sigma}>0$, we
have

$\mathcal{L}_{0*}(\hat{\sigma})=-\mathcal{J}_{*}(\hat{\sigma})=-\sum_{i\in
I}\langle x_{i}|\hat{\sigma}|x_{i}\rangle\cdot|y_{i}\rangle\langle y_{i}|$

which implies

$\begin{split}\sum_{i\in I}\langle x_{i}|\hat{\sigma}|x_{i}\rangle
p_{ij}=-\sum_{i\in I}\langle x_{i}|\hat{\sigma}|x_{i}\rangle\langle
x_{j}|\mathcal{L}_{0*}^{-1}(\ket{y_{i}}\bra{y_{i}})x_{j}\rangle=\\\
-\left\langle x_{j}\left|\mathcal{L}_{0*}^{-1}\left(\sum_{i\in I}\langle
x_{i}|\hat{\sigma}|x_{i}\rangle\ket{y_{i}}\bra{y_{i}}\right)\right|x_{j}\right\rangle=\langle
x_{j}|\hat{\sigma}|x_{j}\rangle\end{split}$

so the stationary state of $\mathbf{P}$ is

$\pi(i):=\frac{\langle x_{i}|\hat{\sigma}|x_{i}\rangle}{\sum_{j\in I}\langle
x_{j}|\hat{\sigma}|x_{j}\rangle}$

which is fully supported since $\hat{\sigma}>0$.

The waiting times are not exponentially distributed as in the case of a
classical continuous time Markov process, instead their probability density
function after observing a click of the type $i$ is given by:

$f_{i}(t):=-{\rm
tr}(\mathcal{L}_{0*}e^{t\mathcal{L}_{0*}}(\ket{y_{i}}\bra{y_{i}}).$ (31)

We now introduce the quantities used in the result of this section:

  * 1.

asymptotic value of $T_{I}(k)/k$:

$\langle t_{I}\rangle:=-\sum_{i\in I}\pi(i){\rm
tr}\left(\mathcal{L}_{0*}^{-1}(\ket{y_{i}}\bra{y_{i}})\right);$

  * 2.

average of 1-norm of $\mathcal{L}_{0*}^{2}$ in stationarity:

$b_{r}^{2}:=\sum_{i\in
I}\pi(i)\left\|\mathcal{L}_{0*}^{-2}(\ket{y_{i}}\bra{y_{i}})\right\|_{1};$

  * 3.

superoperator norm of $\mathcal{L}^{-1}_{0}$:

$c_{r}:=\left\|\mathcal{L}_{0}^{-1}\right\|_{\infty\rightarrow\infty}=\|\mathcal{L}_{0}^{-1}(\mathbf{1})\|_{\infty}.$

The last equality in the expression of $c_{r}$ is due to Theorem 20 in
Appendix C and makes the superoperator norm analytically computable.

######  Theorem 13 (Fluctuations of FPT for Total Counts in Reset Processes).

Assume that Hypothesis 2 holds ($\mathcal{L}$ be irreducible) the jump
operators are of the form (29) (reset process). Let $\varepsilon$ be the
spectral gap of $\mathbf{P}^{\dagger}\mathbf{P}$. For every $\gamma>0$:

$\begin{split}&\mathbb{P}_{\nu}\left(\frac{T_{I}(k)}{k}\geq\langle
t_{I}\rangle+\gamma\right)\leq
C(\nu)\exp\left(-k\frac{\gamma^{2}\varepsilon}{4b_{r}^{2}}h\left(\frac{5c_{r}\gamma}{2b_{r}^{2}}\right)\right)\\\
{\rm and}\\\ &\mathbb{P}_{\nu}\left(\frac{T_{I}(k)}{k}\leq\langle
t_{I}\rangle-\gamma\right)\leq
C(\nu)\exp\left(-k\frac{\gamma^{2}\varepsilon}{4b_{r}^{2}}h\left(\frac{5c_{r}\gamma}{2b_{r}^{2}}\right)\right),\quad
k\in\mathbb{N},\end{split}$

where $h(x):=(\sqrt{1+x}+\frac{x}{2}+1)^{-1}$ and $C(\nu):=(\sum_{i\in
I}\nu(i)^{2}/\pi(i))^{\frac{1}{2}}$. Here, $\mathbb{P}_{\nu}$ is the
probability measure induced by the initial state given by

$\sum_{i\in I}\nu(i)\ket{y_{i}}\bra{y_{i}},\quad\sum_{i\in
I}\nu(i)=1,\quad\nu(i)\geq 0.$

######  Corollary 14.

The variance of the first passage time for total counts is bounded from above
by:

$\frac{{\rm
var}_{\pi}(T_{I}(k))}{k}\leq\left(1+\frac{2}{\varepsilon}\right)b_{r}^{2}.$

The proof of Theorem 13 can be found in Appendix C.5. Note that a classical
Markov chain can be embedded into a quantum Markov process, by setting $H=0$,
$I=\mathfrak{E}$, and the jump operators
$L_{ij}=\sqrt{w_{ij}}\ket{x_{j}}\bra{x_{i}}$ for an orthonormal basis
$\\{\ket{x_{j}}\\}_{j=1}^{d}$.

####  3.2.4 Tail Bound for General Counting Observables

Our final result provides the quantum analogue to the bound of Theorem 5. We
consider the FPT $T_{\mathfrak{A}}(k)$ for the observable
$N_{\mathfrak{A}}(t)$ which counts the number of jumps with label in the
subset $\mathfrak{A}\subseteq I$, cf. (24). The next result gives an upper
bound to the tails of the FPT distribution under the assumption that
Hypothesis 2 holds.

Recall that we introduced the generator decomposition

$\mathcal{L}=\mathcal{J}_{\mathfrak{A}}+\mathcal{L}_{\infty},$

where $\mathcal{J}_{\mathfrak{A}}(x)=\sum_{i\in\mathfrak{A}}L_{i}^{*}xL_{i}$.
We denote

$\beta:=\left\|\mathcal{L}_{\infty*}^{-1}\right\|_{1\rightarrow 1}.$

######  Theorem 15 (Rare Fluctuations of General Quantum Counting Observable
FPTs).

Assume that Hypothesis 2 holds ($\mathcal{L}$ be irreducible), and let
$\mathfrak{A}\subseteq I$ be nonempty. For every $\gamma>\beta-\langle
t_{\mathfrak{A}}\rangle$:

$\mathbb{P}_{\nu}\left(\frac{T_{\mathfrak{A}}(k)}{k}\geq\langle
t_{\mathfrak{A}}\rangle+\gamma\right)\leq\exp\left(-k\left(\frac{\gamma+\langle
t_{\mathfrak{A}}\rangle-\beta}{\beta}-\log\left(\frac{\gamma+\langle
t_{\mathfrak{A}}\rangle}{\beta}\right)\right)\right),k\in\mathbb{N}.$

The proof of Theorem 15 can be found in Appendix C.6. As mentioned above, and
in contrast to the classical case, in general there is no explicit expression
for the $1\rightarrow 1$ norm of a superoperator, but thanks to Theorem 20, we
know that

$\beta=\|\mathcal{L}_{\infty}^{-1}\|_{\infty\rightarrow\infty}=\|\mathcal{L}_{\infty}^{-1}(\mathbf{1})\|_{\infty}.$

Despite being in general computational demanding, at least there exists an
explicit formula for the new expression for $\beta$. We can also derive an
upper bound on the variance, in terms of $\beta$, stated below.

######  Corollary 16.

Given any non-empty set of jumps $\mathfrak{A}$, the variance of the
corresponding first passage time at stationarity is bounded from above by:

$\frac{{\rm
var}_{\varsigma}(T_{\mathfrak{A}}(k))}{k}\leq\left(1+\frac{2}{\tilde{\varepsilon}}\right)\beta^{2},$

where

$\tilde{\varepsilon}:=1-\max\\{\|\Psi(x)\|_{\infty\to\infty}:\|x\|_{\infty\to\infty}=1,\,{\rm
tr}(\varsigma x)=0\\}.$

The proof of Corollary 16 can be found in the Appendix C.6.

###  3.3 Examples: Quantum Concentration Bounds

In this section we illustrate the quantum concentration results obtained in
the second part of the paper with a few simple examples.

####  3.3.1 Three-Level Emitter with Dephasing Channel

We consider a three-level system, with one dissipative jump and one dephasing
channel, as sketched in Fig. 6 (a). The system has Hamiltonian

$H=\Omega_{01}(|0\rangle\langle 1|+|1\rangle\langle
0|)+\Omega_{12}(|1\rangle\langle 2|+|2\rangle\langle 1|)$

and jump operators

$L_{1}=\omega_{12}\ket{1}\bra{2},\qquad L_{2}=\omega_{02}(|0\rangle\langle
0|-|2\rangle\langle 2|)$

We count the total number of jumps of both the emission channel and the
dephasing channel and compare the lower bounds on the large deviation rate
function obtained from Theorems 11 and 15 with the exact rate function, see
Fig. 6(b). The exact rate function (full/black) is bounded in the entire
region by Theorem 11 (dashed/blue). Theorem 15 for general counting observable
allows one to bound (dotted/red) the right tail of the rate function: as in
the classical case, cf. Fig. 2, this tail bound is tighter than the activity
bound for large enough deviations.

Figure 6: Bounds on the rate function of the FPT of the total number of
emissions for a quantum three-level system. (a) Sketch of quantum three-level
system. The Hamiltonian (dashed/blue) drives the evolution coherently while
the jump operators (solid/red) give rise to dissipative transitions. (b) Exact
rate function $I(T_{I}(k)/k)$ (full/black) of the FPT for the total number of
quantum jumps, for the case $\Omega_{01}=10$, $\Omega_{12}=1$,
$\omega_{12}=\Omega_{01}$, $\omega_{02}=\frac{1}{5}\Omega_{01}$. Theorem 11
gives a lower bound on the entire rate function (dashed/blue). Theorem 15
bounds the tail (dotted/red) in the region $T_{I}(k)/k>\beta$.  Figure 7:
Bounds on the rate function of the FPT of the total number of emissions for a
two-level emitter. (a) Sketch of two-level emitter. The Hamiltonian
(dashed/blue) drives the evolution coherently while the jump operators
(solid/red) give rise to dissipative transitions. (b) Exact rate function
$I(T_{I}(k)/k)$ (full/black) of the FPT for the total number of quantum jumps,
for the case $\Omega_{01}=1$, $\omega_{01}=0.8\Omega_{01}$. As this is a
quantum reset process, Theorem 13 gives a lower bound on the entire rate
function (dashed/blue). Theorem 15 bounds the tail (dotted/red) in the region
$T_{I}(k)/k>\beta$. The result from [33] gives an upper bound on the rate
function (dash-dotted/magenta).

####  3.3.2 Two Level Emitter

We illustrate the results of Theorem 13 by considering a two level emitter
with driving Hamiltonian $H=\Omega_{01}(|0\rangle\langle 1|+|0\rangle\langle
1|)$ and jump operator representing the emitted photon
$L=\omega_{01}\ket{0}\bra{1}$, see Fig. 7(a). Since $L$ is a rank-one
operator, the system jumps to the same state $|0\rangle$ every time there a
count. Therefore, the counts process is a renewal process with waiting
distribution computed using equation (31). In Fig. 7(b) we plot the exact rate
function (full/black) and two lower bounds, obtained from our reset process
bound of Theorem 13 (dashed/blue) and the counting observable bound Theorem 15
(dotted/red). For comparison to known literature we plot the upper bound on
the rate function (dot-dashed/magenta) of reset processes obtained via large
deviations [33]. As in the classical example of Sec. 2.3.1, the bound of
Theorem 15 outperforms that of Theorem 13 for larger deviations.

Figure 8: Lower bound on the FPT rate function for a counting observable of a
quantum three-level system. Exact rate function $I(T_{\mathfrak{A}}(k)/k)$
(full/black) of the FPT only counting the dephasing jumps (jump operator by
$L_{2}$), for the same model of Fig. 6(a). Theorem 15 gives a lower bound on
right deviations (dotted/red) in the region $T_{\mathfrak{A}}(k)/k>\beta$.

####  3.3.3 Three Level Emitter Counting Dephasing Jumps

For our final example we consider a system in which we are only interested in
a subset of jumps. We use the same setup as in Sec. 3.3.1 but this time we
only count the number of dephasing jumps (jump operator $L_{2}$). In Fig. 8 we
show the exact rate function (full/black) and a lower bound on its right tail
from Theorem 15 (dotted/red).

##  4 Conclusions

When studying stochastic dynamics one often considers a description in terms
of stochastic trajectories of fixed overall time and where (time-integrated)
observables fluctuate. But there is an alternative description of the same
dynamics in terms of trajectories of fluctuating overall time but where one or
more observables have a fixed value. It is of interest therefore to formulate
general results about dynamics in these two alternative descriptions. This is
what we have done in this paper for concentration bounds, by complementing the
concentration inequalities for time-integrated quantities of Refs. [43, 44] by
analogous concentration bounds for first passage times in both systems with
classical or quantum Markov dynamics.

The study of FPTs is more involved that that of time-integrated observables,
and for that reason we were only able to derive bounds for FTPs for the subset
of all trajectory functions known as counting observables (which include
fundamental quantities such as the dynamical activity). The concentration
inequalities that we find are upper bounds on the probabilities to observe
fluctuations in FTPs, and are valid for all values of the observable threshold
that defines the FTP and not only in the large threshold limit where large
deviation theory applies. The bounds are written in terms of relatively simple
quantities which describe the overall properties of the dynamics (and which in
an ideal setting can be determined by observation), in particular the longest
expected waiting time between events, and the spectral gap of the symmetrised
generator (these and similar spectral quantities have been shown to be
relevant in other recent works such as [62, 63]). Our upper bounds on
fluctuations complement the lower bounds from so-called thermodynamic
uncertainty relations, thus together providing general two-sided constraints
to the likelihood of fluctuations.

While our results should have wide applicability in the theory of Markov
processes and non-equilibrium statistical mechanics, a possible area for
further study is their application in constructing confidence intervals for
parameter estimation ([44, Section 5.5]). It is also possible to apply
analogous perturbative techniques as those used here to systems with discrete
time dynamics to derive similar results. Also, a better understanding of the
transition operators in Eqs. (9) and (25) may allow the derivation of FPT
bounds for arbitrary fluctuations of FPTs of generic counting observables,
rather than just the tails of their distributions. A further extension is to
FPTs of empirical currents, which are of of great interest in the study of
non-equilibrium dynamics. Finally, it would be useful to bound the spectral
gap in terms of further simpler quantities related to the physics of the
process, which would provide more intuitive and and operationally accessible
concentration bounds.

Acknowledgments This work was supported by the EPSRC grants EP/R04421X/1 and
EP/V031201/1. F.G. has been partially supported by the MUR grant Dipartimento
di Eccellenza 2023–2027 of Dipartimento di Matematica, Politecnico di Milano
and by the INDAM GNAMPA project 2024 “Probabilità quantistica e applicazioni”.

##  Appendix A Upper Bounds on Fluctuations of FPTs for Classical Markov
Processes

###  A.1 Proof of Lemma 1

######  Lemma 1.

The following statements hold true:

  1. 1.

$\overline{\lambda}:=-\max\\{\Re(z):z\in{\rm Sp}(\mathbf{L}_{\infty})\\}>0$,
hence $\mathbf{L}_{\infty}$ is invertible;

  2. 2.

$r(\mathbf{R}^{-1}\mathbf{W}_{2})<1,$ therefore $\sum_{k\geq 0}\mathbf{S}^{k}$
is well defined with $\mathbf{S}=\mathbf{R}^{-1}\mathbf{W}_{2}$ and one has

$-\frac{{\bf 1}}{\mathbf{L}_{\infty}}=\sum_{k\geq 0}\left(\frac{{\bf
1}}{\mathbf{R}}\mathbf{W}_{2}\right)^{k}\frac{{\bf 1}}{\mathbf{R}},$

  3. 3.

for every $u<\overline{\lambda}$, one has

$\mathbb{E}_{\nu}[e^{uT_{\mathfrak{A}}(k)}]=\left\langle\nu,\left(\frac{\mathbf{L}_{\infty}}{u+\mathbf{L}_{\infty}}\mathbf{Q}\right)^{k}\underline{1}\right\rangle,$

  4. 4.

$\left\|\mathbf{L}_{\infty}^{-1}\right\|^{-1}_{\infty\rightarrow\infty}\leq\overline{\lambda}$.

###### Proof.

Note that $\mathbf{L}_{\infty}$ generates a sub-Markov semigroup
$e^{t\mathbf{L}_{\infty}}$. By Perron-Frobenius theory we know that

$r(e^{t\mathbf{L}_{\infty}})=e^{-t\overline{\lambda}}\Leftrightarrow\overline{\lambda}:=-\max\\{\Re(z):\,z\in{\rm
Sp}(\mathbf{L}_{\infty})\\}.$

By contradiction suppose $\overline{\lambda}=0$. Then there exists a nonzero
nonnegative function $f:E\rightarrow[0,+\infty)$ such that
$\mathbf{L}_{\infty}f=0$. We then have

$\mathbf{L}f=\mathbf{L}_{\infty}f+\mathbf{W}_{1}f=\mathbf{W}_{1}f\geq 0.$

Therefore one has

$0=\langle\hat{\pi},\mathbf{L}f\rangle=\langle\hat{\pi},\mathbf{W}_{1}f\rangle,$

which implies that $\mathbf{L}f=\mathbf{W}_{1}f=0$ because $\hat{\pi}$ has
full support. Since $\mathbf{L}$ is irreducible, $f=\alpha\underline{1}$ for
some nonnegative $\alpha$, however $\alpha\mathbf{W}_{1}\underline{1}=0$
implies that $\alpha$ and therefore $f$ are $0$ (it follows from the
positivity of $\mathbf{W}_{1}$). We came to a contradiction, which proves that
$\overline{\lambda}>0$. Therefore ${\rm
Sp}(\mathbf{L}_{\infty})\subset\\{z\in\mathbb{C}:\,\Re(z)\leq-\overline{\lambda}<0\\}$
and $\mathbf{L}_{\infty}$ is invertible.

2\. The proof is similar to that of point 1. Notice that
$\mathbf{R}^{-1}\mathbf{W}_{2}$ is a sub-Markov transition kernel and let
$r=r(\mathbf{R}^{-1}\mathbf{W}_{2})$ such that $r\in[0,1]$, and the
corresponding nonzero nonnegative eigenvector $f:E\rightarrow[0,+\infty)$.
Suppose that $r=1$, then we can write

$(\mathbf{P}-{\bf
1})f=\mathbf{R}^{-1}\mathbf{W}_{1}f+(\mathbf{R}^{-1}\mathbf{W}_{2}-{\bf
1})f=\mathbf{R}^{-1}\mathbf{W}_{1}f,$

therefore

$0=\langle\pi,(\mathbf{P}-{\bf
1})f\rangle=\langle\pi,\mathbf{R}^{-1}\mathbf{W}_{1}f\rangle,$

which implies that $\mathbf{R}^{-1}\mathbf{W}_{1}f=(\mathbf{P}-{\bf 1})f=0$
from which it follows that $f=0$ as before, hence a contradiction. What we
have proved so far shows that the derivation of Eq. (9) is correct.

3\. Using Dyson expansion, one can see that

$\mathbb{P}_{\nu}(T_{\mathfrak{A}}(k)\leq t)=\int_{\sum_{i=1}^{k}t_{i}\leq
t}\langle\nu,e^{t_{1}\mathbf{L}_{\infty}}\mathbf{W}_{1}e^{(t_{2})\mathbf{L}_{\infty}}\cdots\mathbf{W}_{1}e^{\left(t-\sum_{i=1}^{k}t_{i}\right)\mathbf{L}_{\infty}}\underline{1}\rangle
dt_{1}\cdots dt_{k}.$

Therefore, if $u<\overline{\lambda}$, then

$-\frac{{\bf
1}}{u+\mathbf{L}_{\infty}}=\int_{0}^{+\infty}e^{t(u+\mathbf{L}_{\infty})}dt$
(32)

and we get

$\mathbb{E}_{\nu}[e^{uT_{\mathfrak{A}}(k)}]=\left\langle\nu,\left(-\frac{{\bf
1}}{u+\mathbf{L}_{\infty}}\mathbf{W}_{1}\right)^{k}\underline{1}\right\rangle.$

4\. The Spectral Mapping Theorem implies that ${\rm
Sp}(\mathbf{L}_{\infty}^{-1})=\\{z^{-1}:\,z\in{\rm
Sp}(\mathbf{L}_{\infty})\\}$, therefore one has that

$\left\|\frac{{{\bf
1}}}{{\mathbf{L}_{\infty}}}\right\|_{\infty\rightarrow\infty}\geq
r(\mathbf{L}_{\infty}^{-1})\geq\frac{1}{\overline{\lambda}}\quad\Leftrightarrow\quad\left\|\frac{{{\bf
1}}}{{\mathbf{L}_{\infty}}}\right\|_{\infty\rightarrow\infty}^{-1}\leq\overline{\lambda}.$

∎

###  A.2 Proof of Theorem 2

######  Theorem 2.

Let us consider any nonempty subset $\mathfrak{A}$ of the set of possible
jumps. The collection of corresponding FPTs $\\{T_{\mathfrak{A}}(k)/k\\}$
satisfies a LDP with good rate function given by

$I_{\mathfrak{A}}(t):=\sup_{u\in\mathbb{R}}\\{ut-\log(r(u))\\}$

where

$r(u)=\begin{cases}r\left(\mathbf{Q}_{u}\right)&\text{ if
}u<\overline{\lambda}\\\ +\infty&\text{o.w.}\end{cases}$

where $\mathbf{Q}_{u}:=-(u+\mathbf{L}_{\infty})^{-1}\mathbf{W}_{1}$ and
$\overline{\lambda}:=-\max\\{\Re(z):z\in{\rm Sp}(\mathbf{L}_{\infty})\\}.$

###### Proof.

The proof of Lemma 1 shows that if
$u<\overline{\lambda}:=-\max\\{\Re(z):z\in{\rm Sp}(\mathbf{L}_{\infty})\\}$,
then

$\mathbb{E}_{\nu}[e^{uT_{\mathfrak{A}}(k)}]=\left\langle\nu,\mathbf{Q}_{u}^{k}\underline{1}\
\right\rangle,$ (33)

where $\mathbf{Q}_{u}:=-(u+\mathbf{L}_{\infty})^{-1}\mathbf{W}_{1}$. From the
expression

$\mathbf{Q}_{u}=\int_{0}^{+\infty}e^{(u+\mathbf{L}_{\infty})t}\mathbf{W}_{1}dt$

one sees that $\mathbf{Q}_{u}$ is a positivity preserving map for every
$u<\overline{\lambda}$. From Perron-Frobenius theory (see Theorem 19 in
Appendix C.7), we know that $r(u):=r(\mathbf{Q}_{u})$ is an eigenvalue of
$\mathbf{Q}_{u}$ that admits a positive eigenvector $x(u)$. With simple
algebraic manipulations one can see that

$\mathbf{Q}_{u}x(u)=r(u)x(u)\Leftrightarrow\mathbf{L}_{s(u)}x(u)=-ux(u)$

where $\mathbf{L}_{s(u)}:=\mathbf{L}+(e^{s(u)}-1)\mathbf{W}_{1}$ and
$s(u)=-\log(r(u))$.

The perturbations of $\mathbf{L}$ given by $\mathbf{L}_{s}$ for
$s\in\mathbb{R}$ are irreducible (see Lemma 22 in Appendix C.7), hence they
admit a unique positive eigenvector, which is actually strictly positive and
corresponds to the the eigenvalue given by $\max\\{\Re(z):z\in{\rm
Sp}(\mathbf{L}_{s})\\}$. Therefore, $-u=\max\\{\Re(z):z\in{\rm
Sp}(\mathbf{L}_{s(u)})\\}$ and $x(u)>0$ is the unique eigenvector for
$\mathbf{Q}_{u}$ corresponding to $r(u)$. One can also show that $r(u)$ is in
fact algebraically simple for $\mathbf{Q}_{u}$ as in the proof of Lemma 5.3 in
[64].

Summing up, one has that for $u<\overline{\lambda}$ the function $u\mapsto
r(u)$ is smooth (actually analytic in a complex neighborhood of the values we
are considering) and

$\lim_{k\rightarrow+\infty}\frac{1}{k}\log(\mathbb{E}_{\nu}[e^{uT_{\mathfrak{A}}(k)}])=\log(r(u)).$
(34)

Indeed,

$\frac{1}{k}\log(\mathbb{E}_{\nu}[e^{uT_{\mathfrak{A}}(k)}])\leq\frac{1}{k}\log(\|\mathbf{Q}_{u}^{k}\|_{\infty\rightarrow\infty})\rightarrow_{k\rightarrow+\infty}\log(r(u))$

thanks to Gelfand’s formula. On the other hand, using (33) and assuming that
$\|x(u)\|_{\infty}\leq 1$, one has

$\frac{1}{k}\log(\mathbb{E}_{\nu}[e^{uT_{\mathfrak{A}}(k)}])\geq\log(r(u))+\frac{1}{k}\log(\langle\nu,x(u)\rangle)\rightarrow_{k\rightarrow+\infty}\log(r(u)),$

since $x(u)>0$ and $\langle\nu,x(u)\rangle>0$.

In order to apply Gärtner-Ellis Theorem ([12, Theorem 2.3.6]), we only need to
show that

$\lim_{u\uparrow\overline{\lambda}}\log(r(u))=\lim_{u\uparrow\overline{\lambda}}\log(r(u))^{\prime}=+\infty.$
(35)

Notice that $r(u)$ and $\log(r(u))^{\prime}=r^{\prime}(u)/r(u)$ are both
monotone non-decreasing (they are limits of monotone non-decreasing functions
cf. Eq. (34)): the limits in Eq. (35) exist and we only need to show that they
cannot be finite.

Let $\mathbf{T}$ be the spectral projection of $\mathbf{L}_{\infty}$
corresponding to $-\overline{\lambda}$; we remark that $\mathbf{L}_{\infty}$
restricted to the range of $\mathbf{T}$ is diagonalisable. To show this, let
us assume that this is not the case. If $-\overline{\lambda}$ is an eigenvalue
of $\mathbf{L}_{\infty}$, then $0$ is an eigenvalue of
$\mathbf{L}^{\prime}:=\mathbf{L}_{\infty}+\overline{\lambda}{\bf 1}$. The
matrix $\mathbf{L}^{\prime}$ restricted to the range $\mathbf{T}$ is also not
diagonalisable. However, this means that the restriction contains a Jordan
block, in which case the norm of $e^{t\mathbf{L}^{\prime}}$ explodes for large
$t$ which contradicts the fact that $e^{t\mathbf{L}^{\prime}}$ generates a
contraction semigroup by Lumer-Phillips Theorem (see, for instance, Theorem
3.15 and the following corollaries in [65]).

Let us first show that

$\lim_{u\uparrow\overline{\lambda}}r(u)=+\infty.$

Notice that $\mathbf{T}\mathbf{Q}\neq 0$, since
$\mathbf{T}\mathbf{Q}(\underline{1})=\mathbf{T}\underline{1}\neq 0$. Therefore

$\mathbf{Q}_{u}=\frac{\mathbf{L}_{\infty}}{\mathbf{L}_{\infty}+u}\mathbf{Q}=\frac{\overline{\lambda}}{\overline{\lambda}-u}\mathbf{T}\mathbf{Q}+({\bf
1}-\mathbf{T})\frac{\mathbf{L}_{\infty}}{u+\mathbf{L}_{\infty}}\mathbf{Q}$

has a norm that explodes for $u\uparrow\overline{\lambda}$. By contradiction,
let us assume that for $u\uparrow\overline{\lambda}$, $r(u)\uparrow
r(\overline{\lambda})<+\infty$. This implies that we can choose $x(u)$ such
that it converges to the unique strictly positive Perron-Frobenius eigenvector
of $\mathbf{L}_{s(\overline{\lambda})}$ and that $\min{\rm
Sp}(x(u))\not\rightarrow 0.$ Therefore we have for every $0\leq
u<\overline{\lambda}$

$\|\mathbf{Q}_{u}\|_{\infty\rightarrow\infty}=\|\mathbf{Q}_{u}(\underline{1})\|_{\infty}\leq\frac{1}{\min{\rm
Sp}(x(u))}\|\mathbf{Q}_{u}(x(u))\|_{\infty}=r(u)\frac{\|x(u)\|_{\infty}}{\min{\rm
Sp}(x(u))}$

. Since the right side remains finite as $u\uparrow\bar{\lambda}$, this
contradicts the fact that $\|{\bf Q}_{u}\|_{\infty\to\infty}$ diverges. Notice
that the first equality in the previous Eq. is due to Theorem 20 in Appendix
C.7.

Let $l(u)$ be the left eigenvector of $\mathbf{Q}_{u}$; we can assume that
$\langle l(u),x(u)\rangle\equiv 1$, therefore one has

$\begin{split}r(u)&=\langle
l(u),-(u+\mathbf{L}_{\infty})^{-1}\mathbf{W}_{1}x(u)\rangle\\\
&=\underbrace{\langle
l(u),-(u+\mathbf{L}_{\infty})^{-1}\mathbf{T}\mathbf{W}_{1}x(u)\rangle}_{(I)}+\underbrace{\langle
l(u),-(u+\mathbf{L}_{\infty})^{-1}(\mathbf{1}-\mathbf{T})\mathbf{W}_{1}x(u)\rangle}_{(II)}.\\\
\end{split}$

Since $(II)$ stays bounded, for $u\uparrow\overline{\lambda}$ one has

$r(u)\asymp\frac{\overline{\lambda}}{\overline{\lambda}-u}\langle
l(u),\mathbf{T}\mathbf{Q}x(u)\rangle$

with both sides diverging as $u\uparrow\bar{\lambda}$. Differentiating the
previous expression for $r(u)$ and dividing for $r(u)$ one gets

$\begin{split}\frac{r^{\prime}(u)}{r(u)}&=\frac{\langle
l(u),(u+\mathbf{L}_{\infty})^{-2}\mathbf{W}_{1}x(u)\rangle}{r(u)}\\\
&=\underbrace{\frac{\overline{\lambda}}{(\overline{\lambda}-u)^{2}}\frac{\langle
l(u),\mathbf{T}\mathbf{Q}x(u)\rangle}{r(u)}}_{(I)}+\underbrace{\frac{\langle
l(u),(u+\mathbf{L}_{\infty})^{-2}({\bf
1}-\mathbf{T})\mathbf{W}_{1}x(u)\rangle}{r(u)}}_{(II)}.\end{split}$

When $u\uparrow\overline{\lambda}$, $(II)\rightarrow 0$, while
$(I)\asymp(\overline{\lambda}-u)^{-1}$ and we are done. ∎

###  A.3 Proof of Theorem 3 and Corollary 4

######  Theorem 3 (Fluctuations of FPT for Activity).

Suppose Hypothesis 1 holds ($\mathbf{L}$ is irreducible) and let $\varepsilon$
be the spectral gap of $\mathbf{P}^{\dagger}\mathbf{P}$. For every $\gamma>0$
the following holds true:

$\begin{split}&\mathbb{P}_{\nu}\left(\frac{T_{\mathfrak{E}}(k)}{k}\geq\langle
t_{\mathfrak{E}}\rangle+\gamma\right)\leq
C(\nu)\exp\left(-k\frac{\gamma^{2}\varepsilon}{4b_{c}^{2}}h\left(\frac{5c_{c}\gamma}{2b_{c}^{2}}\right)\right)\\\
{\rm and}\\\ &\mathbb{P}_{\nu}\left(\frac{T_{\mathfrak{E}}(k)}{k}\leq\langle
t_{\mathfrak{E}}\rangle-\gamma\right)\leq
C(\nu)\exp\left(-k\frac{\gamma^{2}\varepsilon}{4b_{c}^{2}}h\left(\frac{5c_{c}\gamma}{2b_{c}^{2}}\right)\right),\quad
k\in\mathbb{N},\end{split}$

where $h(x):=(\sqrt{1+x}+\frac{x}{2}+1)^{-1}$ and $C(\nu):=\max_{x\in
E}\left\\{\nu(x)/\pi(x)\right\\}$.

###### Proof.

We begin by using the Chernoff bound to upper bound the probability of
$T_{\mathfrak{E}}(k)/k$ right deviating from $\langle t_{\mathfrak{E}}\rangle$
by more than $\gamma>0$, using the moment generating function:

$\mathbb{P}_{\nu}\left(\frac{T_{\mathfrak{E}}(k)}{k}\geq\langle
t_{\mathfrak{E}}\rangle+\gamma\right)\leq e^{-ku(\langle
t_{\mathfrak{E}}\rangle+\gamma)}\mathbb{E}_{\nu}[e^{uT_{\mathfrak{E}}(k)}],\quad
u\geq 0.$ (36)

We now focus on upper bounding the moment generating function using the
definition in Eq. (5). Introducing the notation

$\mathbf{F}_{u}:=\frac{\mathbf{R}}{\mathbf{R}-u},\quad u<R_{\min},$

one has that for every $0\leq u<R_{\min}$ the following holds true:

$\begin{split}\mathbb{E}_{\nu}[e^{uT_{\mathfrak{E}}(k)}]&=\left\langle\nu,(\mathbf{F}_{u}\mathbf{P})^{k}\underline{1}\right\rangle=\left\langle\frac{\nu}{\pi},(\mathbf{F}_{u}\mathbf{P})^{k}\underline{1}\right\rangle_{\pi}\\\
&=\left\langle\mathbf{F}_{u}^{\frac{1}{2}}\frac{\nu}{\pi},(\mathbf{F}_{u}^{\frac{1}{2}}\mathbf{P}\mathbf{F}_{u}^{\frac{1}{2}})^{k-1}\mathbf{F}_{u}^{\frac{1}{2}}\underline{1}\right\rangle_{\pi}\\\
&\leq\left\|\mathbf{F}_{u}^{\frac{1}{2}}\frac{\nu}{\pi}\right\|_{\pi}\left\|\mathbf{F}_{u}^{\frac{1}{2}}\mathbf{P}\mathbf{F}_{u}^{\frac{1}{2}}\right\|_{\pi}^{k-1}\left\|\mathbf{F}_{u}^{\frac{1}{2}}\underline{1}\right\|_{\pi},\end{split}$

where $\frac{\nu}{\pi}(x)=\frac{\nu(x)}{\pi(x)},\forall x\in E$ and, with a
little abuse of notation, we denote $\|\cdot\|_{\pi\rightarrow\pi}$ instead by
$\|\cdot\|_{\pi}$. We use the notation $\mathbf{M}_{\frac{\nu}{\pi}}$ to
denote the multiplication operator corresponding to $\frac{\nu}{\pi}$. We can
write the following:

$\left\|\mathbf{F}_{u}^{\frac{1}{2}}\frac{\nu}{\pi}\right\|_{\pi}=\left\|\mathbf{F}_{u}^{\frac{1}{2}}\mathbf{M}_{\frac{\nu}{\pi}}\underline{1}\right\|_{\pi}=\left\|\mathbf{M}_{\frac{\nu}{\pi}}\mathbf{F}_{u}^{\frac{1}{2}}\underline{1}\right\|_{\pi}\leq\left\|\mathbf{M}_{\frac{\nu}{\pi}}\right\|_{\pi}\left\|\mathbf{F}_{u}^{\frac{1}{2}}\underline{1}\right\|_{\pi}=\left\|\frac{\nu}{\pi}\right\|_{\infty}\left\|\mathbf{F}_{u}^{\frac{1}{2}}\underline{1}\right\|_{\pi}.$

Note that
$\|\mathbf{M}_{\frac{\nu}{\pi}}\|_{\pi}=\|\frac{\nu}{\pi}\|_{\infty}$ since we
know that $\mathbf{M}_{\frac{\nu}{\pi}}$ is a diagonal matrix. Applying Lemma
23 with $f=\mathbf{F}_{u}^{\frac{1}{2}}\underline{1}$, Lemma 24 with
$\mathbf{A}=\mathbf{B}=\mathbf{F}_{u}^{\frac{1}{2}}$ and remembering that
$\mathbf{F}_{u}^{\frac{1}{2}}$ is self adjoint one can derive the following
inequalities:

  1. 1.

$\left\|\mathbf{F}_{u}^{\frac{1}{2}}\underline{1}\right\|_{\pi}\leq\left\|\mathbf{F}_{u}^{\frac{1}{2}}\hat{\mathbf{P}}\mathbf{F}_{u}^{\frac{1}{2}}\right\|_{\pi}^{\frac{1}{2}}$,

  2. 2.

$\left\|\mathbf{F}_{u}^{\frac{1}{2}}\mathbf{P}\mathbf{F}_{u}^{\frac{1}{2}}\right\|_{\pi}\leq\left\|\mathbf{F}_{u}^{\frac{1}{2}}\hat{\mathbf{P}}\mathbf{F}_{u}^{\frac{1}{2}}\right\|_{\pi}$,

where we recall that $\hat{\mathbf{P}}$ is the León-Perron matrix associated
to $\mathbf{P}$, cf. equation (14). Therefore, we get:

$\mathbb{E}_{\nu}[e^{uT_{\mathfrak{E}}(k)}]\leq\left\|\frac{\nu}{\pi}\right\|_{\infty}\left\|\mathbf{F}_{u}^{\frac{1}{2}}\hat{\mathbf{P}}\mathbf{F}_{u}^{\frac{1}{2}}\right\|_{\pi}^{k},\quad
0\leq u<R_{\min}.$ (37)

If we set $C(\nu):=\left\|\frac{\nu}{\pi}\right\|_{\infty}$, the problem is
now reduced to finding an upper bound on
$\left\|\mathbf{F}_{u}^{\frac{1}{2}}\hat{\mathbf{P}}\mathbf{F}_{u}^{\frac{1}{2}}\right\|_{\pi}$.
Notice that
$\mathbf{F}_{u}^{\frac{1}{2}}\hat{\mathbf{P}}\mathbf{F}_{u}^{\frac{1}{2}}$ is
self adjoint, therefore its norm coincide with its spectral radius $r(u)$.
Moreover,
$\mathbf{F}_{u}^{\frac{1}{2}}\hat{\mathbf{P}}\mathbf{F}_{u}^{\frac{1}{2}}$ is
similar to $\hat{\mathbf{P}}\mathbf{F}_{u}$, hence they share the same
spectral radius; finally, Perron-Frobenius theory ensures that $r(u)$ is an
eigenvalue of $\mathbf{P}(u):=\hat{\mathbf{P}}\mathbf{F}_{u}$.

We can write $\mathbf{P}(u)$ as a power series:

$\mathbf{P}(u)=\hat{\mathbf{P}}+\sum_{l=1}^{\infty}u^{l}\hat{\mathbf{P}}\left(\frac{{\bf
1}}{\mathbf{R}}\right)^{l},\quad 0\leq u<R_{\min}.$ (38)

For conciseness of notation, we denote $\mathbf{D}:=\mathbf{R}^{-1}$.
Perturbation theory (see for instance [66]) implies that, if we can bound
$\|\hat{\mathbf{P}}\mathbf{D}^{l}\|_{\pi}\leq\delta\zeta^{l-1}$ for some
$\delta,\zeta>0$ and $l>1$, within the range
$|u|<(2\delta\varepsilon^{-1}+\zeta)^{-1}$ \- with $\varepsilon$ the spectral
gap of $\hat{\mathbf{P}}$ (which is equal to the absolute spectral gap of
$\mathbf{P}$). The spectral radius $r(u)$ can be expressed in the following
way:

$r(u)=1+\sum_{l=1}^{\infty}u^{l}r^{(l)},$ (39)

where:

$r^{(l)}=\sum_{p=1}^{l}\frac{(-1)^{p}}{p}\sum_{\begin{subarray}{c}\nu_{1}+\dots+\nu_{p}=l,\,\nu_{i}\geq
1\\\ \mu_{1}+\dots+\mu_{p}=p-1,\,\mu_{j}\geq 0\end{subarray}}{\rm
tr}\left(\hat{\mathbf{P}}\mathbf{D}^{\nu_{1}}\mathbf{S}^{(\mu_{1})}\cdots\hat{\mathbf{P}}\mathbf{D}^{\nu_{p}}\mathbf{S}^{(\mu_{p})}\right),$
(40)

with $\mathbf{S}^{(0)}=-\Pi$, $\mathbf{S}^{(1)}=(\hat{\mathbf{P}}-{\bf
1}+\Pi)^{-1}-\Pi=-\varepsilon^{-1}({\bf 1}-\Pi)$ and $\mathbf{S}^{(\mu)}$ the
$\mu^{\rm th}$ power of $\mathbf{S}^{(1)}$. Note that $\mathbf{S}^{(1)}$ is
equal to the Moore-Penrose inverse of $-({\bf 1}-\hat{\bf P})$ and
$\|\mathbf{S}^{(\mu)}\|_{\pi}=\varepsilon^{-\mu}$ for $\mu\geq 1$. If we set
our estimates $\delta=\zeta=c_{c}:=R_{\min}^{-1}$, we can indeed bound
$\|\hat{\mathbf{P}}\mathbf{D}^{l}\|_{\pi}$ by:

$\|\hat{\mathbf{P}}\mathbf{D}^{l}\|_{\pi}\leq c_{c}^{l},$

which gives a radius of convergence
$|u|<\frac{\varepsilon}{c_{c}(2+\varepsilon)}<\frac{1}{c_{c}}=R_{\min}$. Using
equation (40), we can explicitly determine $r^{(1)}=\langle
t_{\mathfrak{E}}\rangle$ and
$r^{(2)}=b_{c}^{2}-\left\langle\mathbf{D}\underline{1},{\bf
S}^{(1)}\hat{\mathbf{P}}\mathbf{D}\underline{1}\right\rangle_{\pi}$. We then
seek to bound $r^{(l)}$ for $l\geq 3$. For $p=1$:

$-{\rm
tr}(\hat{\mathbf{P}}\mathbf{D}^{l}(-\Pi))=\left\langle\mathbf{D}^{l}\underline{1},\underline{1}\right\rangle_{\pi}=\sum_{x\in
E}\pi(x)\frac{1}{R_{x}^{l}}.$

For the $p\geq 2$ cases, we get:

$\begin{split}-{\rm
tr}(\hat{\mathbf{P}}\mathbf{D}^{\nu_{1}}\mathbf{S}^{(\mu_{1})}\cdots\hat{\mathbf{P}}\mathbf{D}^{\nu_{p}}\mathbf{S}^{(\mu_{p})})&=\left\langle\mathbf{D}\underline{1},\mathbf{D}^{\nu_{1}-1}\mathbf{S}^{(\mu_{1})}\hat{\mathbf{P}}\mathbf{D}^{\nu_{2}}\mathbf{S}^{(\mu_{2})}\cdots\hat{\mathbf{P}}\mathbf{D}^{\nu_{p-1}}\mathbf{S}^{(\mu_{p-1})}\hat{\mathbf{P}}\mathbf{D}^{\nu_{p}-1}\mathbf{D}\underline{1}\right\rangle_{\pi}\\\
&\leq\|\mathbf{D}\underline{1}\|_{\pi}^{2}\|\mathbf{D}\|_{\pi}^{l-2}\|\mathbf{S}^{(1)}\|_{\pi}^{p-1},\end{split}$

where we have taken $\mu_{p}=0$, which is justified since
$\mu_{1}+\cdots+\mu_{p}=p-1$, there is at least one $\mu_{j}=0$, and the trace
is cyclic. Again using Cauchy-Schwarz we can bound the terms as follows:
$\|\mathbf{S}^{(1)}\|_{\pi}=\frac{1}{\varepsilon}$,
$\|\mathbf{D}\|_{\pi}=c_{c}$,
$\|\mathbf{D}\underline{1}\|_{\pi}^{2}=b_{c}^{2}$. We also have that
$\varepsilon\leq 1$. For $p\geq 2$, each term in the inner sum of equation
(40) is then bounded by:

$b_{c}^{2}\frac{c_{c}^{l-2}}{\varepsilon^{l-1}}.$

From [51] the number of terms $N(l)$ in equation (40) is bounded by:

$N(l)=\sum_{p=1}^{n}\binom{l-1}{p-1}\binom{2(p-1)}{p-1}\frac{1}{p}\leq
5^{l-2},$ (41)

which is valid for $l\geq 3$. Combining everything together, the bound on each
$r^{(l)}$ becomes:

$|r^{(l)}|\leq\left\langle\mathbf{D}^{l}\underline{1},\underline{1}\right\rangle_{\pi}+5^{l-2}b_{c}^{2}\frac{c_{c}^{l-2}}{\varepsilon^{l-1}}=\left\langle\mathbf{D}^{l}\underline{1},\underline{1}\right\rangle_{\pi}+\frac{b_{c}^{2}}{5c_{c}}\left(\frac{5c_{c}}{\varepsilon}\right)^{l-1}.$

Which, through a simple computation is in fact valid for $l=2$ as well.
Therefore, the eigenvalue $r(u)$ can be bounded above by:

$\begin{split}r(u)&\leq 1+\langle t_{\mathfrak{E}}\rangle
u+\sum_{l=2}^{\infty}\left\langle\mathbf{D}^{l}\underline{1},\underline{1}\right\rangle_{\pi}u^{l}+\frac{b_{c}^{2}u}{5c_{c}}\left(\frac{5c_{c}u}{\varepsilon}\right)^{l-1}\\\
&\leq\exp\left(\langle t_{\mathfrak{E}}\rangle
u+\sum_{l=2}^{\infty}\left\langle\mathbf{D}^{l}\underline{1},\underline{1}\right\rangle_{\pi}u^{l}+\frac{b_{c}^{2}u}{5c_{c}}\left(\frac{5c_{c}u}{\varepsilon}\right)^{l-1}\right),\end{split}$

where we have used the fact that $1+x\leq e^{x}$. We can further bound this by
focusing on the latter two terms inside the exponential:

  1. 1.

$\sum_{l=2}^{\infty}\langle\mathbf{D}^{l}{\underline{1}},{\underline{1}}\rangle_{\pi}u^{l}\leq\sum_{l=2}^{\infty}b_{c}^{2}c_{c}^{l-2}u^{l}=b_{c}^{2}\frac{u^{2}}{1-c_{c}u}$

  2. 2.

$\begin{split}\sum_{l=2}^{\infty}\frac{b_{c}^{2}u}{5c_{c}}\left(\frac{5c_{c}u}{\varepsilon}\right)^{l-1}&=\sum_{l=2}^{\infty}\frac{b_{c}^{2}u^{2}}{\varepsilon}\left(\frac{5c_{c}u}{\varepsilon}\right)^{l-2}\\\
&=\frac{b_{c}^{2}u^{2}}{\varepsilon}\left(1-\frac{5c_{c}u}{\varepsilon}\right)^{-1}.\\\
\end{split}$

The power series for point 1. again gives a radius of convergence of $0\leq
u<\frac{1}{c_{c}}$. Point 2. gives a radius of convergence of $0\leq
u<\frac{\varepsilon}{5c_{c}}<\frac{\varepsilon}{c_{c}(2+\varepsilon)}<\frac{1}{c_{c}}$.
Combining these terms together and using the upper bound on the Laplace
transform in equation (37), we have, for $0<u<\frac{\varepsilon}{5c_{c}}$:

$\mathbb{E}_{\nu}[e^{(uT_{\mathfrak{E}}(k))}]\leq
C(\nu)\exp\left(k\left(\langle t_{\mathfrak{E}}\rangle
u+b_{c}^{2}u^{2}\left(\frac{1}{1-c_{c}u}+\frac{1}{\varepsilon-5c_{c}u}\right)\right)\right).$
(42)

Since $1-c_{c}u>\varepsilon-5c_{c}u$, we can relax slightly the bound on the
moment generating function, such that when we apply the Chernoff bound in
equation (36), we get that:

$\mathbb{P}_{\nu}\left(\frac{T_{\mathfrak{E}}(k)}{k}\geq\langle
t_{\mathfrak{E}}\rangle+\gamma\right)\leq C(\nu)\exp\left(-k\left(\gamma
u-\frac{2b_{c}^{2}u^{2}}{\varepsilon}\left(1-\frac{5c_{c}u}{\varepsilon}\right)^{-1}\right)\right).$
(43)

Consider the more general expression below, with $\alpha,\beta>0$:

$\gamma u-\alpha u^{2}\left(1-\beta u\right)^{-1}.$

Elementary calculations show that, for $|u|<\frac{1}{\beta}$:

$\sup_{u}\left\\{\gamma u-\alpha u^{2}\left(1-\beta
u\right)^{-1}\right\\}=\frac{\gamma^{2}}{2\alpha}h\left(\frac{\beta\gamma}{\alpha}\right)$
(44)

where $h(x):=(1+\frac{x}{2}+\sqrt{1+x})^{-1}$. In our case,
$\alpha=\frac{2b_{c}^{2}}{\varepsilon}$, $\beta=\frac{5c_{c}}{\varepsilon}$.
Therefore taking the infimum on the right hand side of the bound in (43),
which is valid $\forall u\in[0,\frac{\varepsilon}{5c_{c}})$, yields the final
result for right deviations:

$\mathbb{P}_{\nu}\left(\frac{T_{\mathfrak{E}}(k)}{k}\geq\langle
t_{\mathfrak{E}}\rangle+\gamma\right)\leq
C(\nu)\exp\left(-k\frac{\gamma^{2}\varepsilon}{4{b_{c}^{2}}}h\left(\frac{5c_{c}\gamma}{2b_{c}^{2}}\right)\right).$

To prove the concentration inequality for left deviations, we write the
Chernoff bound for this case, this time with $u\leq 0$:

$\mathbb{P}_{\nu}\left(\frac{T_{\mathfrak{E}}(k)}{k}\leq\langle
t_{\mathfrak{E}}\rangle-\gamma\right)\leq e^{-ku(\langle
t_{\mathfrak{E}}\rangle-\gamma)}\mathbb{E}_{\nu}[e^{uT_{\mathfrak{E}}(k)}].$

We can repeat the proof for right deviations, due to the fact we are upper
bounding the absolute value of the terms in the expansion of (40) for $l\geq
2$. We obtain an upper bound on the moment generating function:

$\mathbb{E}_{\nu}[e^{(uT_{\mathfrak{E}}(k))}]\leq
C(\nu)\exp\left(k\left(\langle t_{\mathfrak{E}}\rangle
u+b_{c}^{2}u^{2}\left(\frac{1}{1-c_{c}|u|}+\frac{1}{\varepsilon-5c_{c}|u|}\right)\right)\right),$

which is valid for $0\leq|u|<\frac{\varepsilon}{5c_{c}}$. One obtains a
concentration bound in terms of $u$ of a similar form to (43), which when
optimised over the allowed $u$ gives the final result for left deviations and
concludes the proof of Theorem 3:

$\mathbb{P}_{\nu}\left(\frac{T_{\mathfrak{E}}(k)}{k}\leq\langle
t_{\mathfrak{E}}\rangle-\gamma\right)\leq
C(\nu)\exp\left(-k\frac{\gamma^{2}\varepsilon}{4{b_{c}^{2}}}h\left(\frac{5c_{c}\gamma}{2b_{c}^{2}}\right)\right).$

∎

######  Corollary 4.

The variance of the first passage time for the total activity at stationarity
is bounded from above by:

$\frac{{\rm
var}_{\pi}(T_{\mathfrak{E}}(k))}{k}\leq\left(1+\frac{2}{\varepsilon}\right)b_{c}^{2}.$

###### Proof.

Notice that for $u\geq 0$ small enough, one has

$\begin{split}\log(\mathbb{E}_{\pi}[e^{uT_{\mathfrak{E}}(k)}])&=\langle
t_{\mathfrak{E}}\rangle ku+\frac{1}{2}{\rm
var}_{\pi}(T_{\mathfrak{E}}(k))u^{2}+o(u^{2})\\\ &\leq
k\log(r(u))=kr^{\prime}(0)u+\frac{k}{2}(r^{\prime\prime}(0)-(r^{\prime}(0))^{2})u^{2}+o(u^{2})\end{split}$

where $r(u)$ is given by equation (39). We recall that

$r^{\prime}(0)=r^{(1)}=\langle
t_{\mathfrak{E}}\rangle=\langle\mathbf{D}\underline{1},\underline{1}\rangle_{\pi},\quad
r^{\prime\prime}(0)=2r^{(2)}=2\langle\mathbf{D}\underline{1},\mathbf{D}\underline{1}\rangle_{\pi}+2\left\langle\mathbf{D}\underline{1},\frac{\hat{\mathbf{P}}}{{\bf
1}-\hat{\mathbf{P}}}\mathbf{D}\underline{1}\right\rangle_{\pi}$

therefore

$r^{\prime\prime}(0)-(r^{\prime}(0))^{2}=\langle{\bf
D}\underline{1},\underline{1}\rangle_{\pi}^{2}+2\left\langle\mathbf{D}\underline{1},\frac{{\bf
1}}{{\bf
1}-\hat{\mathbf{P}}}\mathbf{D}\underline{1}\right\rangle_{\pi}\leq\left(1+\frac{2}{\varepsilon}\right)b_{c}^{2}.$

Hence ${\rm
var}_{\pi}(T_{\mathfrak{E}}(k))\leq\left(1+\frac{2}{\varepsilon}\right)b_{c}^{2}k$.

∎

##  Appendix B Proof of Theorem 5, Corollary 6 and Corollary 7

######  Theorem 5 (Rare Fluctuations of General Counting Observable FPTs).

Let $\mathbf{L}$ be irreducible and $\mathfrak{A}\subseteq\mathfrak{E}$ be
nonempty. For every $k\in\mathbb{N}$ and $\gamma>\beta-\langle
t_{\mathfrak{A}}\rangle$

$\mathbb{P}_{\nu}\left(\frac{T_{\mathfrak{A}}(k)}{k}\geq\langle
t_{\mathfrak{A}}\rangle+\gamma\right)\leq\exp\left(-k\left(\frac{\gamma+\langle
t_{\mathfrak{A}}\rangle-\beta}{\beta}-\log\left(\frac{\gamma+\langle
t_{\mathfrak{A}}\rangle}{\beta}\right)\right)\right).$

###### Proof.

The proof begins with the same procedure as Theorems 3 and 11, but differs in
that we do not use the $L_{2}(\pi)$ Hilbert space. We again begin by applying
Chernoff bound:

$\mathbb{P}_{\nu}\left(\frac{T_{\mathfrak{A}}(k)}{k}\geq\langle
t_{\mathfrak{A}}\rangle+\gamma\right)\leq e^{-uk(\langle
t_{\mathfrak{A}}\rangle+\gamma)}\mathbb{E}_{\nu}[e^{uT_{\mathfrak{A}}(k)}],\quad
u>0.$ (45)

The next step is to upper bound the Laplace transform: for $0\leq
u<\|\mathbf{L}_{\infty}^{-1}\|^{-1}_{\infty\rightarrow\infty}$ one has

$\begin{split}\mathbb{E}_{\nu}[e^{uT_{\mathfrak{A}}(k)}]&=\left\langle\nu,\left(\frac{{\bf
1}}{{\bf
1}+\frac{u}{\mathbf{L}_{\infty}}}\mathbf{Q}\right)^{k}\underline{1}\right\rangle\\\
&=\left\langle\nu,\left(\sum_{i=0}^{\infty}u^{i}\left(-\frac{{\bf
1}}{\mathbf{L}_{\infty}}\right)^{i}\mathbf{Q}\right)^{k}\underline{1}\right\rangle\\\
&\leq\underbrace{\|\nu\|_{1}}_{=1}\left(\sum_{i=0}^{\infty}u^{i}\left\|\frac{{\bf
1}}{\mathbf{L}_{\infty}}\right\|_{\infty\rightarrow\infty}^{i}\right)^{k}\underbrace{\|\underline{1}\|_{\infty}}_{=1}.\end{split}$

If we denote $\beta:=\left\|\mathbf{L}_{\infty*}^{-1}\right\|_{1\rightarrow
1}$, then for $u<\frac{1}{\beta}$:

$\mathbb{E}_{\nu}[e^{uT_{\mathfrak{A}}(k)}]\leq\left(\frac{1}{1-\beta
u}\right)^{k}=\exp\left(-k\log(1-\beta u)\right).$ (46)

Placing this back into equation (45) we get:

$\mathbb{P}_{\nu}\left(\frac{T_{\mathfrak{A}}(k)}{k}\geq\langle
t_{\mathfrak{A}}\rangle+\gamma\right)\leq\exp\left(-k\left(u(\gamma+\langle
t_{\mathfrak{A}}\rangle)+\log(1-\beta u)\right)\right),\quad 0\leq
u<\beta^{-1}.$ (47)

The minimum of the RHS is achieved at

$u^{*}=\frac{1}{\beta}-\frac{1}{\gamma+\langle
t_{\mathfrak{A}}\rangle}=\frac{\gamma+\langle
t_{\mathfrak{A}}\rangle-\beta}{\beta(\gamma+\langle
t_{\mathfrak{A}}\rangle)}.$

We have $u^{*}<\beta^{-1}$, and $u^{*}>0$ if $\gamma>\beta-\langle
t_{\mathfrak{A}}\rangle$. Substituting $u^{*}$ into equation (47) gives the
final result:

$\mathbb{P}_{\nu}\left(\frac{T_{\mathfrak{A}}(k)}{k}\geq\langle
t_{\mathfrak{A}}\rangle+\gamma\right)\leq\exp\left(-k\left(\frac{\gamma+\langle
t_{\mathfrak{A}}\rangle-\beta}{\beta}-\log\left(\frac{\gamma+\langle
t_{\mathfrak{A}}\rangle}{\beta}\right)\right)\right).$

This concludes the proof of Theorem 5. ∎

######  Corollary 6.

Given any non-empty set of jumps $\mathfrak{A}$, the variance of the
corresponding first passage time at stationarity is bounded from above by:

$\frac{{\rm
var}_{\varphi}(T_{\mathfrak{A}}(k))}{k}\leq\left(1+\frac{2}{\tilde{\varepsilon}}\right)\beta^{2},$

where

$\tilde{\varepsilon}:=1-\max\\{\|\mathbf{Q}f\|_{\infty}:\|f\|_{\infty}=1,\,\langle\varphi,f\rangle=0\\}.$

###### Proof.

From the proof of Lemma 17 one can see that

$\begin{split}\frac{{\rm
var}_{\varphi}[T_{\mathfrak{A}}(k)]}{k}&=\left\langle\varphi,\mathbf{L}_{\infty}^{-2}\underline{1}\right\rangle^{2}+2\left\langle\varphi,\mathbf{L}_{\infty}^{-1}({\bf
1}-\Pi_{\varphi})\mathbf{L}_{\infty}^{-1}\underline{1}\right\rangle\\\
&+\frac{2}{k}\left\langle\varphi,\mathbf{L}_{\infty}^{-1}\sum_{i=2}^{k}\sum_{j=1}^{i-1}\mathbf{Q}^{j}({\bf
1}-\Pi_{\varphi})\mathbf{L}_{\infty}^{-1}\underline{1}\right\rangle\\\
&\leq\left(1+2\left(1+\frac{1}{k}\sum_{i=2}^{k}\sum_{j=1}^{i-1}(1-\tilde{\varepsilon})^{j}\right)\right)\beta^{2}\\\
&=\left(1+\frac{2}{\tilde{\varepsilon}}\right)\beta^{2}-\frac{2((1-\tilde{\varepsilon})-(1-\tilde{\varepsilon})^{k+1})}{k\tilde{\varepsilon}^{2}}\beta^{2}\\\
&\leq\left(1+\frac{2}{\tilde{\varepsilon}}\right)\beta^{2}.\end{split}$

∎

######  Corollary 7 (Simple Upper Bound on $\beta$).

For general counting observables, the norm
$\beta:=\left\|\mathbf{L}_{\infty}^{-1}\right\|_{\infty\rightarrow\infty}$ is
bounded from above by:

$\beta\leq
c_{c}\tilde{k}\max_{(x,y)\notin\mathfrak{A}}\left\\{\frac{R_{x}}{w_{xy}}\right\\}^{\tilde{k}-1}\max_{(x,y)\in\mathfrak{A}}\left\\{\frac{R_{x}}{w_{xy}}\right\\}\leq
c_{c}\tilde{k}\left(\frac{R_{\rm max}}{w_{\rm
min}}\right)^{\tilde{k}}=:\tilde{\beta},$

with $c_{c},R_{\rm max},w_{\rm min}$ defined in Eqs. (16), (18), and
respectively (19). The concentration bound in Theorem 5 holds with $\beta$
replaced by any of the two upper bounds above.

###### Proof.

From the expression (8) for $-\mathbf{L}_{\infty}^{-1}$ we obtain

$-\frac{{\bf 1}}{\mathbf{L}_{\infty}}=\sum_{k=0}^{\infty}\left(\frac{{\bf
1}}{\mathbf{R}}\mathbf{W}_{2}\right)^{k}\frac{{\bf 1}}{\mathbf{R}}.$

Let $\tilde{k}>0$ be the minimax jump distance as it has been defined before
Corollary 7, i.e. the maximum over all states of the minimum number of jumps
which suffice to get from that stat to a final jump between states in
$\mathfrak{A}$. The previous sum can be written in the following way:

$\sum_{l=0}^{\infty}\left(\frac{{\bf
1}}{\mathbf{R}}\mathbf{W}_{2}\right)^{l}=\sum_{m=0}^{\tilde{k}-1}\left(\frac{{\bf
1}}{\mathbf{R}}\mathbf{W}_{2}\right)^{m}\sum_{n=0}^{\infty}\left(\frac{{\bf
1}}{\mathbf{R}}\mathbf{W}_{2}\right)^{\tilde{k}n},$

where we break up $l$ into multiples of $\tilde{k}$ and a remainder term,
since $\mathbb{N}_{0}=\cup_{m=0}^{\tilde{k}-1}m+\tilde{k}\mathbb{N}_{0}$. We
can upper bound as

$\beta=\left\|\frac{{\bf
1}}{\mathbf{L}_{\infty*}}\right\|_{\infty\rightarrow\infty}\leq\left\|\frac{{\bf
1}}{\mathbf{R}}\right\|_{\infty\rightarrow\infty}\sum_{m=0}^{\tilde{k}-1}\left\|\frac{{\bf
1}}{\mathbf{R}}\mathbf{W}_{2}\right\|_{\infty\rightarrow\infty}^{m}\sum_{n=0}^{\infty}\left\|\left(\frac{{\bf
1}}{\mathbf{R}}\mathbf{W}_{2}\right)^{\tilde{k}}\right\|_{\infty\rightarrow\infty}^{n}.$

Notice that $\left\|\mathbf{R}^{-1}\right\|_{\infty\rightarrow\infty}=c_{c}$.
As $\mathfrak{A}$ is non-empty, the spectral radius of
$\mathbf{R}^{-1}\mathbf{W}_{2}$ is strictly less than 1 (see Lemma 1 ii));
therefore, there exists a $k$ such that
$\left\|\left(\mathbf{R}^{-1}\mathbf{W}_{2}\right)^{k}\right\|_{1\rightarrow
1}\leq q<1$. We will now show that $k$ can be taken equal to $\tilde{k}$; in
this case, we can write the upper bound of $\beta$ in terms of $q$ as:

$\beta\leq c_{c}\tilde{k}\frac{1}{1-q}.$ (48)

So we just need to find $q$. Note that for any matrix ${\bf G}$ with positive
entries, one has $\|{\bf G}\|_{1\rightarrow
1}=\|G\underline{1}\|_{\infty}=\max_{x\in
E}\langle\delta_{x},G\underline{1}\rangle$. Therefore

$\left\|\left(\frac{{\bf
1}}{\mathbf{R}}\mathbf{W}_{2}\right)^{\tilde{k}}\right\|_{1\rightarrow
1}=\left\langle\delta_{x_{0}},\left(\frac{{\bf
1}}{\mathbf{R}}\mathbf{W}_{2}\right)^{\tilde{k}}\underline{1}\right\rangle,$
(49)

where $x_{0}$ is the state which attains the norm. From the structure of the
generator, we know that

$\frac{{\bf
1}}{\mathbf{R}}\mathbf{W}_{2}\underline{1}=\underline{1}-\frac{{\bf
1}}{\mathbf{R}}\mathbf{W}_{1}\underline{1}.$ (50)

By the definition of the minimax jump distance, we know that there exists a
path $x_{0},\dots,x_{l}$ that happens with positive probability and such that
$(x_{l-1},x_{l})\in\mathfrak{A}$. We can rewrite the right side of (49) as

$\begin{split}&\left\langle\delta_{x_{0}},\left(\frac{{\bf
1}}{\mathbf{R}}\mathbf{W}_{2}\right)^{\tilde{k}}\underline{1}\right\rangle\leq\left\langle\delta_{x_{0}},\left(\frac{{\bf
1}}{\mathbf{R}}\mathbf{W}_{2}\right)^{l}\underline{1}\right\rangle=\\\
&\left\langle\delta_{x_{0}},\left(\frac{{\bf
1}}{\mathbf{R}}\mathbf{W}_{2}\right)^{l-1}\underline{1}\right\rangle-\left\langle\delta_{x_{0}},\left(\frac{{\bf
1}}{\mathbf{R}}\mathbf{W}_{2}\right)^{l-1}\left(\frac{{\bf
1}}{\mathbf{R}}\mathbf{W}_{1}\right)\underline{1}\right\rangle=:g_{+}-g_{-}.\end{split}$

In the first inequality we used the fact that $\mathbf{R}^{-1}\mathbf{W}_{1}$
is submarkovian, while in the second equality we made use of Eq. (50). It is
easy to see that $g_{+}\leq 1$. Moreover, we know that

$\begin{split}g_{-}&\geq\frac{w_{x_{0}x_{1}}}{R_{x_{0}}}\cdots\frac{w_{x_{l-1}x_{l}}}{R_{x_{l-1}}}\geq\min_{(x,y)\notin\mathfrak{A}}\left\\{\frac{w_{xy}}{R_{x}}\right\\}^{\tilde{k}-1}\min_{(x,y)\in\mathfrak{A}}\left\\{\frac{w_{xy}}{R_{x}}\right\\}\\\
&\geq\min_{(x,y)\in\mathfrak{E}}\left\\{\frac{w_{xy}}{R_{x}}\right\\}^{\tilde{k}}\geq\left(\frac{w_{\rm
min}}{R_{\max}}\right)^{\tilde{k}}.\end{split}$

Hence we can take

$q=1-\min_{(x,y)\notin\mathfrak{A}}\left\\{\frac{w_{xy}}{R_{x}}\right\\}^{\tilde{k}-1}\min_{(x,y)\in\mathfrak{A}}\left\\{\frac{w_{xy}}{R_{x}}\right\\}\leq
1-\left(\frac{w_{\rm min}}{R_{\rm max}}\right)^{\tilde{k}}.$

Applying this to equation (48), we get that

$\beta\leq
c_{c}\tilde{k}\max_{(x,y)\notin\mathfrak{A}}\left\\{\frac{R_{x}}{w_{xy}}\right\\}^{\tilde{k}-1}\max_{(x,y)\in\mathfrak{A}}\left\\{\frac{R_{x}}{w_{xy}}\right\\}\leq
c_{c}\tilde{k}\left(\frac{R_{\rm max}}{w_{\rm min}}\right)^{\tilde{k}}.$

∎

######  Lemma 17 (Variance of Classical FPTs).

Let $\varphi$ be the invariant measure of $\mathbf{Q}$, cf. Eq (11), and let
$\Pi_{\varphi}$ be the map
$\Pi_{\varphi}:f\mapsto\langle\varphi,f\rangle\underline{1}$. The variance of
the first passage time for counting observables is given by:

$\begin{split}\frac{{\rm
var}_{\varphi}\left(T_{\mathfrak{A}}(k)\right)}{k}=\left\langle\varphi,\mathbf{L}_{\infty}^{-1}\underline{1}\right\rangle^{2}&+2\left\langle\varphi,\mathbf{L}_{\infty}^{-1}\frac{{\bf
1}}{{\bf 1}-\mathbf{Q}}({\bf
1}-\Pi_{\varphi})\mathbf{L}_{\infty}^{-1}\underline{1}\right\rangle\\\
&-\frac{2}{k}\left\langle\varphi,\mathbf{L}_{\infty}^{-1}\frac{\mathbf{Q}-\mathbf{Q}^{k+1}}{({\bf
1}-\mathbf{Q})^{2}}({\bf
1}-\Pi_{\varphi})\mathbf{L}_{\infty}^{-1}\underline{1}\right\rangle,\quad\forall
k\geq 0.\end{split}$ (51)

###### Proof.

We recall the explicit expression for the moment generating function from
Lemma 1

$\mathbb{E}_{\varphi}[e^{uT_{\mathfrak{A}}(k)}]=\left\langle\varphi,\left(\frac{\mathbf{L}_{\infty}}{u+\mathbf{L}_{\infty}}\mathbf{Q}\right)^{k}\underline{1}\right\rangle.$

We can write the first moment as

$\mathbb{E}_{\varphi}[e^{uT_{\mathfrak{A}}(k)}]^{\prime}=-\left\langle\varphi,\sum_{i=1}^{k}\left(\frac{\mathbf{L}_{\infty}}{u+\mathbf{L}_{\infty}}\mathbf{Q}\right)^{i-1}\left(\frac{\mathbf{L}_{\infty}}{(u+\mathbf{L}_{\infty})^{2}}\mathbf{Q}\right)\left(\frac{\mathbf{L}_{\infty}}{u+\mathbf{L}_{\infty}}\mathbf{Q}\right)^{k-i}\underline{1}\right\rangle.$
(52)

At $u=0$ this gives us the form of the asymptotic mean.

$\mathbb{E}_{\varphi}[T_{\mathfrak{A}}(k)]=-k\left\langle\varphi,\mathbf{L}_{\infty}^{-1}\underline{1}\right\rangle.$
(53)

Differentiating equation (52) at $u=0$ gives us the second moment:

$\begin{split}\mathbb{E}_{\varphi}[T_{\mathfrak{A}}(k)^{2}]&=2\left\langle\varphi,\mathbf{L}_{\infty}^{-2}\underline{1}\right\rangle
k+\sum_{i=1}^{k}\left\langle\varphi,\mathbf{L}_{\infty}^{-1}\left(\sum_{j=1}^{i-1}\mathbf{Q}^{i-j}+\sum_{j=1}^{k-i}\mathbf{Q}^{j}\right)\mathbf{L}_{\infty}^{-1}\underline{1}\right\rangle.\\\
&=2\left\langle\varphi,\mathbf{L}_{\infty}^{-2}\underline{1}\right\rangle
k+2\left\langle\varphi,\mathbf{L}_{\infty}^{-1}\sum_{1\leq j<i\leq
k}\mathbf{Q}^{j}\mathbf{L}_{\infty}^{-1}\underline{1}\right\rangle\\\
&=2\left\langle\varphi,\mathbf{L}_{\infty}^{-2}\underline{1}\right\rangle
k+2\sum_{i=2}^{k}\sum_{j=1}^{i-1}\left\langle\varphi,\mathbf{L}_{\infty}^{-1}\underline{1}\right\rangle^{2}\\\
&\qquad\qquad\qquad\quad+2\left\langle\varphi,\mathbf{L}_{\infty}^{-1}\sum_{i=2}^{k}\sum_{j=1}^{i-1}\mathbf{Q}^{j}({\bf
1}-\Pi_{\varphi})\mathbf{L}_{\infty}^{-1}\underline{1}\right\rangle\\\
\end{split}$

where to arrive at the third line, after $\mathbf{Q}^{j}$ we have inserted
$\Pi_{\varphi}+{\bf 1}-\Pi_{\varphi}$, where $\Pi_{\varphi}$ is the projection
onto $\underline{1}$. Using the fact that
$\sum_{i=2}^{k}\sum_{j=1}^{i-1}1=\frac{k}{2}(k-1)$, and recalling equation
(53) for the expression for the first moment, hence

$\begin{split}\frac{{\rm
var}_{\varphi}\left(T_{\mathfrak{A}}(k)\right)}{k}=2\left\langle\varphi,\mathbf{L}_{\infty}^{-2}\underline{1}\right\rangle&-\left\langle\varphi,\mathbf{L}_{\infty}^{-1}\underline{1}\right\rangle^{2}+2\left\langle\varphi,\mathbf{L}_{\infty}^{-1}\frac{\mathbf{Q}}{{\bf
1}-\mathbf{Q}}({\bf
1}-\Pi_{\varphi})\mathbf{L}_{\infty}^{-1}\underline{1}\right\rangle\\\
&-\frac{2}{k}\left\langle\varphi,\mathbf{L}_{\infty}^{-1}\frac{\mathbf{Q}-\mathbf{Q}^{k+1}}{({\bf
1}-\mathbf{Q})^{2}}({\bf
1}-\Pi_{\varphi})\mathbf{L}_{\infty}^{-1}\underline{1}\right\rangle.\end{split}$

Finally, we can again place $\Pi_{\varphi}+{\bf 1}-\Pi_{\varphi}$ in the first
term, in between the two $\mathbf{L}_{\infty}^{-1}$. Rearranging this gives
the final result

$\begin{split}\frac{{\rm
var}_{\varphi}\left(T_{\mathfrak{A}}(k)\right)}{k}=\left\langle\varphi,\mathbf{L}_{\infty}^{-1}\underline{1}\right\rangle^{2}&+2\left\langle\varphi,\mathbf{L}_{\infty}^{-1}\frac{{\bf
1}}{{\bf 1}-\mathbf{Q}}({\bf
1}-\Pi_{\varphi})\mathbf{L}_{\infty}^{-1}\underline{1}\right\rangle\\\
&-\frac{2}{k}\left\langle\varphi,\mathbf{L}_{\infty}^{-1}\frac{\mathbf{Q}-\mathbf{Q}^{k+1}}{({\bf
1}-\mathbf{Q})^{2}}({\bf
1}-\Pi_{\varphi})\mathbf{L}_{\infty}^{-1}\underline{1}\right\rangle.\end{split}$

∎

##  Appendix C Quantum Markov Processes

###  C.1 Proof of Lemma 8

######  Lemma 8.

The generator $\mathcal{L}$ has a unique invariant state if and only if $\Phi$
does. If $\Phi$ is irreducible then $\mathcal{L}$ is irreducible, but the
converse is generally not true.

###### Proof.

Indeed if $\mathcal{L}_{*}(\nu)=0$ for some state $\nu$ then

$\Phi_{*}(\mathcal{J}_{*}(\nu))=-\mathcal{J}_{*}\mathcal{L}_{0*}^{-1}(-\mathcal{L}_{0*}(\nu))=\mathcal{J}_{*}(\nu)$

so $\nu^{\prime}:=\mathcal{J}_{*}(\nu)/{\rm tr}[\mathcal{J}_{*}(\nu)]$ is a
stationary state for $\Phi$. Notice that if $\nu$ is strictly positive, then
this is not necessarily true for $\nu^{\prime}$, depending on the form of the
jump operators. Conversely, if $\Phi_{*}(\nu)=\nu$ for some state $\nu$ then

$\mathcal{L}_{*}[\mathcal{L}_{0*}^{-1}(\nu)]=(\mathcal{L}_{0*}+\mathcal{J}_{*})[\mathcal{L}_{0*}^{-1}(\nu)]=\nu+\mathcal{J}_{*}\mathcal{L}_{0*}^{-1}(\nu)=\nu-\Phi_{*}(\nu)=0$

so $\nu^{\prime}=\mathcal{L}_{0*}^{-1}(\nu)/{\rm
tr}[\mathcal{L}_{0*}^{-1}(\nu)]$ is a stationary state for $\mathcal{L}$. Here
we used the fact that
$-\mathcal{L}^{-1}_{0}=\int_{0}^{\infty}e^{t\mathcal{L}_{0}}$ is completely
positive. If $\Phi$ is irreducible then $\nu>0$ and
$-\mathcal{L}_{0*}^{-1}(\nu)>0$, therefore $\mathcal{L}$ is irreducible, and
Hypothesis 3 implies Hypothesis 2.

∎

###  C.2 Proof of Lemma 9

######  Lemma 9.

Assume that Hypothesis 2 ($\mathcal{L}$ is irreducible) holds. Then the
following statements are true:

  1. 1.

$\overline{\lambda}:=-\max\\{\Re(z):z\in{\rm Sp}({\cal L}_{\infty})\\}>0$,
hence ${\cal L}_{\infty}$ is invertible;

  2. 2.

for every $u<\overline{\lambda}$, one has

$\mathbb{E}_{\rho}[e^{uT_{\mathfrak{A}}(k)}]={\rm
tr}\left(\rho\left((u+\mathcal{L}_{\infty})^{-1}\mathcal{L}_{\infty}\Psi\right)^{k}({\bf
1})\right),$

  3. 3.

$\|{\cal
L}_{\infty}^{-1}\|_{\infty\rightarrow\infty}^{-1}\leq\overline{\lambda}.$

###### Proof.

$\mathcal{L}_{\infty}$ generates a sub-Markov semigroup
$e^{t\mathcal{L}_{\infty}}$. From the Spectral Mapping Theorem, one has that

${\rm Sp}(e^{t\mathcal{L}_{\infty}})=e^{t{\rm
Sp}(\mathcal{L}_{\infty})},\quad\forall t\geq 0.$

Moreover, since $e^{t\mathcal{L}_{\infty}}$ is completely positive, by Perron-
Frobenius Theorem (Theorem 19) the spectral radius and largest eigenvalue of
$e^{t\mathcal{L}_{\infty}}$ coincide. Hence:

$r(e^{t\mathcal{L}_{\infty}})=e^{t\lambda},\lambda:=\max\\{\Re(z):z\in{\rm
Sp}(\mathcal{L}_{\infty})\\},$

and $\exists x\in M_{d}(\mathbb{C})$ with $x\geq 0$:

$\mathcal{L}_{\infty}(x)=\lambda x.$

By contradiction, suppose that $\lambda=0$, then