#  Hoeffding’s inequality for continuous-time Markov chains

Jinpeng Liu , Yuanyuan Liu∗∗ and Lin Zhou∗∗∗ School of Mathematics and
Statistics, Xidian University, Xi’an, Shanxi, 710071, P.R. China, E-mail:
<EMAIL_ADDRESS>
∗∗ School of Mathematics and Statistics, HNP-LAMA, Central South University,
Changsha, Hunan, 410083, P.R. China, E-mail<EMAIL_ADDRESS>
∗∗∗ School of Information Science and Engineering, Hunan Women’s University,
Changsha, Hunan, 410004, P.R. China, E-mail<EMAIL_ADDRESS>
###### Abstract

Hoeffding’s inequality is a fundamental tool widely applied in probability
theory, statistics, and machine learning. In this paper, we establish
Hoeffding’s inequalities specifically tailored for an irreducible and positive
recurrent continuous-time Markov chain (CTMC) on a countable state space with
the invariant probability distribution ${\pi}$ and an
$\mathcal{L}^{2}(\pi)$-spectral gap ${\lambda}(Q)$. More precisely, for a
function $g:E\to[a,b]$ with a mean $\pi(g)$, and given $t,\varepsilon>0$, we
derive the inequality

$\mathbb{P}_{\pi}\left(\frac{1}{t}\int_{0}^{t}g\left(X_{s}\right)\mathrm{d}s-\pi(g)\geq\varepsilon\right)\leq\exp\left\\{-\frac{{\lambda}(Q)t\varepsilon^{2}}{(b-a)^{2}}\right\\},$

which can be viewed as a generalization of Hoeffding’s inequality for
discrete-time Markov chains (DTMCs) presented in [J. Fan et al., J. Mach.
Learn. Res., 22(2022), pp. 6185-6219] to the realm of CTMCs. The key analysis
enabling the attainment of this inequality lies in the utilization of the
techniques of skeleton chains and augmented truncation approximations.
Furthermore, we also discuss Hoeffding’s inequality for a jump process on a
general state space.

Keywords: Continuous-time Markov chains; Hoeffding’s inequality; Spectral gap

##  1 Introduction

Classical Hoeffding’s inequality [26] provides a specific upper bound on the
deviation between the empirical mean of a series of independent and
identically distributed (i.i.d.) random variables and their actual expected
value. To be specific, for i.i.d. random variables $\\{X_{i}$, $i\geq 0\\}$
such that $\mathbb{P}(a\leq{X_{i}}\leq{b})=1$, where $a$ and $b$ are a pair of
real numbers, Hoeffding’s inequality gives us

$\mathbb{P}\left(\frac{1}{n}\sum_{i=0}^{n-1}X_{i}-\mathbb{E}[X_{0}]\geq\varepsilon\right)\leq\exp\left\\{\frac{-2n\varepsilon^{2}}{(b-a)^{2}}\right\\},$

where $\varepsilon$ is a positive real number. It can be seen that Hoeffding’s
inequality guarantees that the probability of the large deviation between the
sample mean and the actual expected value will decrease exponentially with the
increase of the sample size. Based on this, Hoeffding’s inequality has been
widely used in various fields, especially in probability limit theory,
statistical learning theory, machine learning and information theory; see,
[18, 5, 9] and their references therein.

Drawing inspiration from the diverse applications of Hoeffding’s inequality,
researchers have developed various generalizations of this powerful tool. One
fundamental generalization involves extending Hoeffding’s inequality to Markov
processes, thereby removing the assumption of independence among random
variables. This extension allows for the application of Hoeffding’s inequality
in a range of fields, including Markov chain Monte Carlo (MCMC) algorithms,
time series analysis, and multi-armed bandit problems with Markovian rewards;
see, e.g., [27, 37, 11, 10, 20].

There is a wealth of literature available on Hoeffding’s inequality for DTMCs.
For example, Glynn and Ormoneit [23] employed the minorization and drift
conditions to establish a Hoeffding inequality for uniformly ergodic DTMCs. In
the same setting, Boucher [8] utilized the Drazin inverse and obtained similar
results to those in the aforementioned study. More recently, Liu and Liu [31]
derived Hoeffding’s inequality for DTMCs via the solution of Poisson’s
equation, thereby eliminating the need for the aperiodic assumption made in
the previous work [23, 8]. On a different note, Dedecker and Gouëzel [17]
employed the coupling technique to derive a Hoeffding inequality specifically
for geometrically ergodic DTMCs. Building upon this work, Wintenberger [36]
extended the results from Dedecker and Gouëzel [17] to encompass unbounded
functions. Additionally, Paulin [33] developed Marton coupling techniques to
derive McDiarmid’s inequality for DTMCs with a finite mixing time, which
serves as a generalization of Hoeffding’s inequality by replacing the sum of
random variables with a function of random variables.

The spectral gap is another crucial tool for studying Hoeffding’s inequality
for Markov processes. Gillman [22] was the first to utilize the spectral gap
to establish a Hoeffding inequality for a reversible DTMC on a finite state
space. Building upon this initial work, Dinwoodie [19] and Lézaud [30] further
refined the Hoeffding bound in reference [22] using different techniques. As a
significant contribution, León and Perron [28] derived an optimal Hoeffding
inequality via the spectral gap. Miasojedow [32] then extended the result of
León and Perron [28] to geometrically ergodic DTMCs on a general state space,
eliminating the requirement of invertibility. More recently, Fan et al. [20]
developed a time-dependent functional Hoeffding inequality based on the work
of León and Perron [28] and Miasojedow [32]. Additionally, there are other
Hoeffding-type inequalities constructed using methods such as Stein’s method,
regeneration techniques, information-theoretical ideas, and others, as
detailed in reference [12, 1, 35].

In the realm of MCMC algorithms, it is an increasing need to deal with cases
involving CTMCs, and there is empirical evidence that these continuous-time
MCMC algorithms are more efficient than their discrete-time counterparts; see,
e.g., [7, 21, 6]. Moreover, additional algorithms, including diffusion
Metropolis-Hastings type algorithms [34] and time-invariant estimating
equations [4], also rely on the use of concentration inequalities in the
context of CTMCs to control approximation errors. Consequently, there is a
compelling need to develop Hoeffding’s inequality specifically for CTMCs. Choi
and Li [16] built upon the techniques introduced in the works [23] and [8] to
derive a Hoeffding inequality for uniformly ergodic diffusion processes. Liu
and Liu [31], on the other hand, extended the results of [16] to encompass
general continuous-time Markov processes by employing the solution of
Poisson’s equation. Additionally, there are other concentration inequalities
available for CTMCs; see, e.g., [30, 29, 25].

However, the body of research on Hoeffding’s inequality for CTMCs is still
relatively sparse compared to the extensive results available for DTMCs. In
this paper, we will utilize the spectral gap to describe Hoeffding’s
inequality for CTMCs, which serves as a parallel result to the discrete-time
case presented in Fan et al. [20], but the two inequalities display subtle
difference in the presentation of its upper bounds, as shown in Theorems 2.1
and 3.1. Since Theorem 3.1 characterizes the optimal Hoeffding’s inequality
for DTMCs using the spectral gap, see, e.g., [28, 20], this implies that our
result represents the optimal Hoeffding’s inequality for continuous-time case.
A comparison with existing results can be found in Remark 2.2. Meanwhile, we
have to note that there is an additional assumption that $\bar{Q}$ is regular
in Theorems 2.1, which result from essential difference between CTMCs and
DTMCs: for a CTMC with an unbounded $Q$-martix $Q$, the regularity assumption
on $Q$ is usually needed to guarantee the uniqueness of the $Q$-process.

The remainder of this paper is organized as follows. In Section 2, we provide
the necessary background and introduce our version of Hoeffding’s inequality.
Section 3 presents the proof of our main result, utilizing two key tools: the
skeleton chain and the collapsed chain. Finally, in Section 4, we discuss
Hoeffding’s inequlity for jump processes on general state spaces.

##  2 Main Results

As preparation for presenting theorems, we introduce some notations as
follows. Let $\\{X_{t},t\geq 0\\}$ be an irreducible and time-homogeneous CTMC
on a countable state space $E$, and let $P_{t}=(P_{t}(i,j))_{i,j\in E}$ be the
transition function of $X_{t}$. We focus on the case that $X_{t}$ is a
$Q$-process with a totally stable and regular $Q$-matrix $Q=(Q(i,j))_{i,j\in
E}$. Assume that $X_{t}$ is positive recurrent with the unique invariant
probability distribution ${\pi}$. Furthermore, we assume that the state space
$E$ is equipped with a $\sigma$-algebra $\mathcal{B}$ and a $\sigma$-finite
measure $\pi$ on $(E,\mathcal{B})$. Let
$\mathcal{L}^{2}(E,\mathcal{B},\pi):=\\{f:\pi(f^{2})<\infty\\}$ be the set of
all square-integrable functions on $(E,\mathcal{B},\pi)$. For convenience, we
write $\mathcal{L}^{2}(E,\mathcal{B},\pi)$ as $\mathcal{L}^{2}(\pi)$. It is
known that $\mathcal{L}^{2}(\pi)$ is the Hilbert space equipped with the
following inner product and norm:

$\left\langle f,h\right\rangle_{\pi}:=\pi(fh)=\sum_{i\in E}\pi(i)f(i)h(i),\ \
\forall f,h\in\mathcal{L}^{2}(\pi),$ $\|f\|_{\pi,2}:=\sqrt{\left\langle
f,f\right\rangle}_{\pi}=(\pi(f^{2}))^{\frac{1}{2}},\ \ \forall
f\in\mathcal{L}^{2}(\pi).$

For a transition function $P_{t}$ with the invariant measure $\pi$, it can be
extended uniquely to $\mathcal{L}^{2}(\pi)$ as a strongly continuous
contraction semigroup, which acts to the right on functions, i.e.,

$P_{t}f(i)=\sum_{j\in E}P_{t}(i,j)f(j),\ \ \forall i\in E,\ \forall
f\in\mathcal{L}^{2}(\pi).$

According to the ordinary semigroup theory, $P_{t}$ deduces an infinitesimal
generator, which is denoted by $\mathcal{A}$. That is, for any
$f\in\mathcal{L}^{2}(\pi)$, if we have

$\lim_{t\rightarrow 0^{+}}\frac{P_{t}f-f}{t}=g,$ (2.1)

and $g\in\mathcal{L}^{2}(\pi)$, then we define $\mathcal{A}f=g$. Such
functions $f$ consist of the domain of $\mathcal{A}$, denoted by
$\mathcal{D}(\mathcal{A})$.

In Chapter 9 of [14], the $\mathcal{L}^{2}(\pi)$-spectral gap of $X_{t}$,
denoted as $\lambda(Q)$ for convenience, is defined as follows.

######  Definition 2.1.

The chain $X_{t}$ is said to admit an $\mathcal{L}^{2}(\pi)$-spectral gap
$\lambda(Q)$ if

$\lambda(Q):=\inf\left\\{-\langle{\mathcal{A}}f,f\rangle_{\pi}:f\in\mathcal{D}({\mathcal{A}}),\
\|f\|_{\pi,2}=1,\ \pi(f)=0\right\\}>0.$

We call a CTMC $X_{t}$ is (time) reversible if $P_{t}$ satisfies

$\pi(i)P_{t}(i,j)=\pi(j)P_{t}(j,i),\ \ \forall i,j\in E,\ \ t\geq 0,$

which is equivalent to

$\pi(i)Q(i,j)=\pi(j)Q(j,i),\ \ \forall i,j\in E.$

In the case of that $X_{t}$ is reversible and the state space $E$ is finite,
we have

$\lambda(Q)=\lambda_{1},$ (2.2)

where $\lambda_{i}$ is the $i\text{th}$ smallest non-trivial eigenvalue of
$-Q$. For the irreversible case, we have the following symmetrizing procedure.
Let $\hat{P}_{t}=(\hat{P}_{t}(i,j))_{i,j\in E}$ be the dual of $P_{t}$, i.e.,

$\hat{P}_{t}(i,j)=\frac{\pi(j)P_{t}(j,i)}{\pi(i)},\ \ \forall i,j\in E.$

It deduces the adjoint operator $\hat{\mathcal{A}}$ of $\mathcal{A}$ and the
dual $Q$-matrix $\hat{Q}=\big{(}\hat{Q}(i,j)\big{)}_{i,j\in E}$, given by

$\hat{Q}(i,j)=\frac{\pi(j)Q(j,i)}{\pi(i)},\ \ \forall i,j\in E.$ (2.3)

It is easy to check that $\hat{Q}$ has the same invariant distribution $\pi$
as $Q$, and that $\hat{Q}$ is regular if $Q$ is regular, see Theorem 4.70 in
[14]. Furthermore, $\mathcal{A}$ and $\hat{\mathcal{A}}$ lead to a self-
adjoint operator $\bar{\mathcal{A}}=({\mathcal{A}+\hat{\mathcal{A}}})/{2}$.
Similarly, we obtain a reversible $Q$-matrix
$\bar{Q}=\big{(}\bar{Q}(i,j)\big{)}_{i,j\in E}$ with respective to the same
stationary distribution $\pi$ as follows

$\bar{Q}(i,j)=\frac{Q(i,j)+\hat{Q}(i,j)}{2},\ \ \forall i,j\in E.$ (2.4)

According to Corollary 9.3 and Theorem 9.12 in [14], we know that

$\lambda(Q)=\lambda(\bar{Q}).$ (2.5)

Our main result is the following theorem, which yields a Hoeffding type
inequality for CTMCs with the $\mathcal{L}^{2}(\pi)$-spectral gap
$\lambda(Q)$.

######  Theorem 2.1.

Assume that the chain $X_{t}$ admits an $\mathcal{L}^{2}(\pi)$-spectral gap
$\lambda(Q)$, and that the $Q$-matrix $\bar{Q}$ is regular. Then for any
bounded function $g:E\to[a,b]$, and $t,\varepsilon>0$, we have

$\mathbb{P}_{\pi}\left(\frac{1}{t}\int_{0}^{t}g\left(X_{s}\right)\mathrm{d}s-\pi(g)\geq\varepsilon\right)\leq\exp\left\\{-\frac{\lambda(Q)t\varepsilon^{2}}{(b-a)^{2}}\right\\}.$

######  Remark 2.1.

Although both $Q$ and $\hat{Q}$ are regular, $\bar{Q}$ may be not regular, see
[13] for example. Hence the regularity assumption of $\bar{Q}$ can not be
removed.

By Hölder’s inequality, we have the following result directly.

######  Corollary 2.1.

Assume that the assumptions of Theorem 2.1 hold. If the initial measure $\nu$
is absolutely continuous with respect to the invariant distribution $\pi$,
then for any bounded function $g:E\to[a,b]$, and $t,\varepsilon>0$, we have

$\mathbb{P}_{\nu}\left(\frac{1}{t}\int_{0}^{t}g\left(X_{s}\right)\mathrm{d}s-\pi(g)\geq\varepsilon\right)\leq\left\|\frac{\mathrm{d}\nu}{\mathrm{d}\pi}\right\|_{\pi,p}\exp\left\\{-\frac{\lambda(Q)t\varepsilon^{2}}{q(b-a)^{2}}\right\\},$

where

$\left\|\frac{\mathrm{d}\nu}{\mathrm{d}\pi}\right\|_{\pi,p}:=\begin{cases}{\left[\pi\left(\left|\frac{\mathrm{d}\nu}{\mathrm{d}\pi}\right|^{p}\right)\right]^{1/p}},&\text{
if }1<p<\infty,\\\
\operatorname{ess}\sup\left|\frac{\mathrm{d}\nu}{\mathrm{d}\pi}\right|,&\text{
if }p=\infty,\end{cases}$

and

$\frac{1}{p}+\frac{1}{q}=1.$

######  Remark 2.2.

Lézaud [30] was the first to obtain a chernoff-type bound for a finite state
space CTMC via the $\mathcal{L}^{2}(\pi)$-spectral gap $\lambda(Q)$. If the
function $g$ satisfies $\pi(g)=0$, $\|g\|_{\infty}=\|g\|_{\pi,2}^{2}=1$, then
Theorem 3.4 in [30] gives

$\mathbb{P}_{\pi}\left(\frac{1}{t}\int_{0}^{t}g\left(X_{s}\right)\mathrm{d}s\geq\varepsilon\right)\leq\exp\left\\{-\frac{\lambda(Q)t\varepsilon^{2}}{12}\right\\}.$

Under the same assumptions, our result derives a better bound as follows

$\mathbb{P}_{\pi}\left(\frac{1}{t}\int_{0}^{t}g\left(X_{s}\right)\mathrm{d}s\geq\varepsilon\right)\leq\exp\left\\{-\frac{\lambda(Q)t\varepsilon^{2}}{4}\right\\}.$

Note that under the same assumptions as Theorem 2.1 or Corollary 2.1,
Hoeffding’s inequalities are also established by replacing $\lambda(Q)$ by one
of its lower bounds. In the reversible case, if there exists a constant
$\beta>0$ and a fixed state $j\in{E}$ such that

$\mathbb{E}_{i}\left[e^{\beta\tau_{j}}\right]<\infty,\ \ \forall{i}\in{E},$
(2.6)

where $\tau_{j}:=\inf\\{t\geq 0:X_{t}=j\\}$ is the first hitting time to the
state $j$, then

$\lambda(Q)\geq{\beta}.$

Furthermore, (2.6) holds if and only if there exists a function $V\geq 1$ such
that

$QV(i)\leq-\beta{V}(i),\ \ i\neq{j},$

see Theorem 4.1 in [13].

In addition, the $\mathcal{L}^{2}(\pi)$-spectral gap $\lambda(Q)$ can be
characterized by its Dirichlet form $\left(D,\mathcal{D}(D)\right)$, which
will be used in the proof of Theorem 2.1, where $D$ is an operator on
$\mathcal{L}^{2}(\pi)$, defined by

$D(f):=\lim_{t\to 0}\frac{\langle f-P_{t}f,f\rangle_{\pi}}{t},\ \ \forall
f\in\mathcal{L}^{2}(\pi),$

and $\mathcal{D}(D)$ is the domain of $D$, given by

$\mathcal{D}(D)=\left\\{f\in\mathcal{L}^{2}(\pi):D(f)<\infty\right\\}.$

The spectral gap of $D$ is defined by

$\lambda(D):=\inf\left\\{D(f):f\in\mathcal{D}(D),\ \|f\|_{\pi,2}=1,\
\pi(f)=0\right\\}.$

From Theorem 9.1 in [14], we know that

$\lambda(Q)=\lambda(D).$ (2.7)

There is another Dirichlet form $\left(D^{*},\mathcal{D}(D^{*})\right)$, where
$D^{*}$ is an operator on $\mathcal{L}^{2}(\pi)$, defined by

$D^{*}(f):=\frac{1}{2}\sum_{i,j\in
E}\pi(i){Q}(i,j)\left(f(j)-f(i)\right)^{2},\ \ \forall
f\in\mathcal{L}^{2}(\pi),$

and $\mathcal{D}(D^{*})$ is the domain of $D^{*}$, given by

$\mathcal{D}(D^{*})=\left\\{f\in\mathcal{L}^{2}(\pi):D^{*}(f)<\infty\right\\}.$

If $Q$-matrix $\bar{Q}$ is regular, it follows from [13] that $D=D^{*}$ and
$\mathcal{D}(D)=\mathcal{D}(D^{*})$, i.e.,

$\mathcal{K}\text{ is dense in }\mathcal{D}\left(D^{*}\right)\text{ in the
}\|\cdot\|_{D^{*}-\operatorname{norm}}\left(\|f\|_{D^{*}}^{2}:=\|f\|^{2}+D^{*}(f)\right),$
(2.8)

where $\mathcal{K}$ is the set of all functions on $E$ with finite support.

######  Example 2.1 (Irreversible Case).

Consider a CTMC on a finite state space $E=\left\\{0,1,2\right\\}$ with the
$Q$-matrix as follows

$Q=\left(\begin{array}[]{ccc}-2&1&1\\\ 1&-3&2\\\ 1&0&-1\\\
\end{array}\right).$

By calculations, we have

$\pi(0)=\frac{1}{3},\ \ \pi(1)=\frac{1}{9},\ \ \pi(2)=\frac{5}{9}.$

According to (2.3) and (2.4), we can obtain

$\hat{Q}=\left(\begin{array}[]{ccc}-2&1/3&5/3\\\ 3&-3&0\\\ 3/5&2/5&-1\\\
\end{array}\right),\ \ \bar{Q}=\left(\begin{array}[]{ccc}-2&2/3&4/3\\\
2&-3&1\\\ 4/5&1/5&-1\\\ \end{array}\right).$

It is easy to calculate that

$\bar{\lambda}_{1}=\frac{15-\sqrt{15}}{5},\ \
\bar{\lambda}_{2}=\frac{15+\sqrt{15}}{5}.$

Then, combining with (2.2) and (2.5), we have

$\lambda(Q)=\frac{{15-\sqrt{15}}}{5}.$

######  Example 2.2 (Birth and Death Processes).

Consider a birth and death process with death rates $a_{i}$, $1\leq i\leq N$,
and birth rates $b_{i}$, $0\leq i\leq N-1$, $N\leq\infty$.

In the case of $a_{i}=\alpha$ and $b_{i}=\beta$, it follows from [24] that

$\lambda(Q)=\alpha+\beta-{2\sqrt{\alpha\beta}}\cos(\frac{\pi}{N+1}).$

In particular, as $N\rightarrow\infty$ and $\alpha>\beta$, we have

$\lambda(Q)=\alpha+\beta-\lim_{N\rightarrow\infty}{2\sqrt{\alpha\beta}}\cos(\frac{\pi}{N+1})=(\sqrt{\alpha}-\sqrt{\beta})^{2}.$

For general birth and death processes, we can give an estimate of the lower
bound of the spectral gap. Define

$\mu_{1}=1,\ \ \mu_{k}=\frac{b_{1}\cdots b_{k-1}}{a_{2}\cdots a_{k}},\ \ 2\leq
k\leq N\leq\infty.$

If $\sum_{i=0}^{N}\mu_{i}<\infty$ and $\delta:=\sup_{n\in
E}\sum_{j=0}^{n}\mu_{j}\sum_{k=n}^{N}\frac{1}{\mu_{k}b_{k}}<\infty$, then it
follows from Corollary 6.4 in [15] that

$\lambda(Q)\geq\frac{1}{4\delta}.$

##  3 Proof of Theorem 2.2

To prove Theorem 2.1, we initially introduce Hoeffding’s inequality for DTMCs
based on the $\mathcal{L}^{2}(\pi)$-spectral gap. Let $\left\\{X_{k},k\geq
0\right\\}$ be an irreducible and positive recurrent DTMC on the countable
state space $E$. Let $P=(P(i,j))_{i,j\in E}$ and $\pi$ be the one-step
transition matrix and the invariant probability distribution of the chain
$X_{k}$. It is known that each transition matrix $P$ of DTMC can be viewed as
a linear operator acting on $\mathcal{L}^{2}(\pi)$, which acts to the right on
functions, i.e.,

$Pf(i)=\sum_{j\in E}P(i,j)f(j),\ \ \forall i\in E,\forall
f\in\mathcal{L}^{2}(\pi).$

We now introduce the $\mathcal{L}^{2}(\pi)$-spectral gap of $P$, denoted by
$1-\lambda(P)$.

######  Definition 3.1.

The chain $X_{k}$ is said to admit an $\mathcal{L}^{2}(\pi)$-spectral gap
$1-\lambda(P)$ if

$\lambda(P):=\sup\left\\{\langle{P}h,h\rangle_{\pi}:\|h\|_{\pi,2}=1,\
\pi(h)=0\right\\}<1.$ (3.1)

Note that when the state space $E$ is finite and the transition matrix $P$ is
reversible, i.e., $P$ satisfies

$\pi(i)P(i,j)=\pi(j)P(j,i),\ \ \forall i,j\in E,$

then $\lambda(P)$ coincides with the second largest eigenvalue of $P$ (the
largest eigenvalue of $P$ is identically equal to 1). Similar to CTMCs, it is
not difficult to verify that

$\lambda(P)=\lambda(\bar{P}),$ (3.2)

where

$\bar{P}(i,j)=\frac{P(i,j)+\hat{P}(i,j)}{2}\ \ \text{and}\ \
\hat{P}(i,j)=\frac{\pi(j)P(j,i)}{\pi(i)},\ \ \forall i,j\in E.$

According to Theorem 3.3 in [20] and (3.2), we introduce the following
Hoeffding inequality regarding DTMCs with the $\mathcal{L}^{2}(\pi)$-spectral
gap $1-\lambda(P)$.

######  Theorem 3.1.

Assume that the chain $X_{k}$ admits an $\mathcal{L}^{2}(\pi)$-spectral gap
$1-\lambda(P)$. Then for any bounded function $g:E\to[a,b]$, and
$n,\varepsilon>0$, we have

$\mathbb{P}_{\pi}\left(\frac{1}{n}\sum_{k=0}^{n-1}g\left(X_{k}\right)-\pi(g)\geq\varepsilon\right)\leq\exp\left\\{-\frac{1-\max\\{\lambda(P),0\\}}{1+\max\\{\lambda(P),0\\}}\cdot\frac{2n\varepsilon^{2}}{(b-a)^{2}}\right\\}.$

Next, we will derive the proof of Theorem 2.1 into three steps, which are
presented in Subsections 3.1-3.3. In Subsection 3.1, we first introduce a
Hoeffding inequality for finite state CTMCs, employing Theorem 3.1 and the
skeleton chain technique. In Subsection 3.2, we introduce the collapsed chain
and present some basic properties. Finally in Subsection 3.3, we extend the
result established for finite state CTMCs to infinitely state by employing the
results established in Subsections 3.1 and 3.2.

###  3.1 Finite state CTMCs

In this subsection, we present a Hoeffding inequality for a finite state CTMC.
To show this, we introduce the definition of the skeleton chain according to
Chapter 5 of [3]. Given a number $\delta>0$, the DTMC
$\left\\{X_{n\delta},n\geq 1\right\\}$ having the one-step transition matrix
$P^{\delta}=(P^{\delta}(i,j))_{i,j\in{E}}$ (and therefore the $n$-step
transition matrix $P^{n\delta}$) is called the $\delta$-skeleton chain of the
CTMC $\left\\{X_{t},t\geq 0\right\\}$. It is not difficult to verify that
$X_{n\delta}$ and $X_{t}$ have the same invariant probability distribution
$\pi$. In addition, if $X_{t}$ is reversible, then $X_{n\delta}$ is also
reversible. Furthermore, if $X_{t}$ has a finite state space, the transition
matrix $P^{\delta}$ is given by

$P^{\delta}=\exp\left\\{{\delta}Q\right\\}=\sum_{n=0}^{\infty}\frac{\delta^{n}{Q^{n}}}{n!}.$
(3.3)

######  Theorem 3.2.

Assume that the chain $X_{t}$ has a finite state space $E$. Then for any
bounded function $g:E\to[a,b]$, and $t,\varepsilon>0$, we have

$\mathbb{P}_{\pi}\left(\frac{1}{t}\int_{0}^{t}g\left(X_{s}\right)\mathrm{d}s-\pi(g)\geq\varepsilon\right)\leq\exp\left\\{-\frac{\lambda(Q)t\varepsilon^{2}}{(b-a)^{2}}\right\\}.$

###### Proof.

For any $\omega\in\Omega$, $X_{t}(\omega)$ is a right-continuous with left
limits sample function. Furthermore, since $g$ is bounded, the integral
$\frac{1}{t}\int_{0}^{t}g\left(X_{s}\right)\mathrm{d}s$ can be expressed as
the limit of Riemann sums, such as

$\frac{1}{t}\int_{0}^{t}g\left(X_{s}(\omega)\right)\mathrm{d}s=\lim_{k\rightarrow\infty}\frac{1}{k}\sum_{i=0}^{k-1}g\left(X_{it/k}(\omega)\right),$

from which, we know that

$\frac{1}{k}\sum_{i=0}^{k-1}g\left(X_{it/k}\right)\xrightarrow{a.s.}\frac{1}{t}\int_{0}^{t}g\left(X_{s}\right)\mathrm{d}s,$
(3.4)

where $X_{it/k}$ is the $\frac{t}{k}$-skeleton chain of $X_{t}$. It follows
from (3.3) that

$P^{\frac{t}{k}}=\sum_{n=0}^{\infty}\frac{t^{n}}{n!\cdot
k^{n}}Q^{n}=I+\frac{t}{k}Q+o(\frac{1}{k}),$ (3.5)

where $I$ is the identity matrix and $o(\frac{1}{k})$ is the infinitesimal of
higher order with respect to $\frac{1}{k}$.

According to (3.1) and (3.5), we have

$\displaystyle\lambda(P^{\frac{t}{k}})$ $\displaystyle=$
$\displaystyle\sup\left\\{\langle
P^{\frac{t}{k}}f,f\rangle_{\pi}:\|f\|_{\pi,2}=1,\pi(f)=0\right\\}$ (3.6)
$\displaystyle=$
$\displaystyle\sup\left\\{\bigg{<}\left(I+\frac{t}{k}{Q}+o(\frac{1}{k})\right)f,f\bigg{>}_{\pi}:\|f\|_{\pi,2}=1,\pi(f)=0\right\\}$
$\displaystyle=$
$\displaystyle\sup\left\\{1+\Big{<}\frac{t}{k}{Q}f,f\Big{>}_{\pi}+o(\frac{1}{k}):\|f\|_{\pi,2}=1,\pi(f)=0\right\\}$
$\displaystyle=$ $\displaystyle
1+\sup\left\\{\Big{<}\frac{t}{k}{Q}f,f\Big{>}_{\pi}:\|f\|_{\pi,2}=1,\pi(f)=0\right\\}+o(\frac{1}{k})$
$\displaystyle=$ $\displaystyle
1-\frac{t}{k}\inf\left\\{-\langle{Q}f,f\rangle_{\pi}:\|f\|_{\pi,2}=1,\pi(f)=0\right\\}+o(\frac{1}{k}).$

Since the state space $E$ is finite, it is evident from (2.2) and (2.5) that
$\lambda(Q)>0$. In addition, it follows that for any
$f\in\mathcal{L}^{2}(\pi)$, we have $f\in\mathcal{D}(\mathcal{A})$. Thus, when
the state space $E$ is finite, the infinitesimal generator $\mathcal{A}$ is
equal to the $Q$-matrix $Q$. According to Definition 2.1, we can obtain that

$\lambda(Q)=\inf\left\\{-\langle{Q}f,f\rangle_{\pi}:\|f\|_{\pi,2}=1,\
\pi(f)=0\right\\}>0.$ (3.7)

Hence, from (3.6) and (3.7), we have

$\lambda(P^{\frac{t}{k}})=1-\frac{t}{k}\lambda(Q)+o(\frac{1}{k}).$ (3.8)

Since $\lambda(Q)>0$, then for any fixed $t>0$, there exists a positive
constant $K$ such that

$-1<-\frac{t}{k}\lambda(Q)+o(\frac{1}{k})<0,\ \ \forall k>K,$

which implies that

$0<\lambda(P^{\frac{t}{k}})<1,\ \ \forall k>K.$ (3.9)

Furthermore, according to (3.8), we have

$1-\lambda(P^{\frac{t}{k}})=\frac{t}{k}\lambda(Q)+o(\frac{1}{k}).$ (3.10)

Therefore, as $k>K$ and for any $\varepsilon>0$, Theorem 3.1 and (3.9)–(3.10)
give

$\displaystyle\mathbb{P}_{\pi}\left(\frac{1}{k}\sum_{i=0}^{k-1}g\left(X_{it/k}\right)-\pi(g)\geq\varepsilon\right)$
$\displaystyle\leq$
$\displaystyle\exp\left\\{-2\cdot\frac{1-\lambda(P^{\frac{t}{k}})}{1+\lambda(P^{\frac{t}{k}})}\cdot\frac{k\varepsilon^{2}}{(b-a)^{2}}\right\\}$
(3.11) $\displaystyle=$
$\displaystyle\exp\left\\{-2\cdot\frac{\frac{t}{k}{\lambda}(Q)+o(\frac{1}{k})}{2-\frac{t}{k}{\lambda}(Q)+o(\frac{1}{k})}\cdot\frac{k\varepsilon^{2}}{(b-a)^{2}}\right\\}$
$\displaystyle=$ $\displaystyle\exp\left\\{-2\cdot\frac{t{\lambda}(Q)+k\cdot
o(\frac{1}{k})}{2-\frac{t}{k}{\lambda}(Q)+o(\frac{1}{k})}\cdot\frac{\varepsilon^{2}}{(b-a)^{2}}\right\\}.$

Applying (3.4) and Fatou’s lemma, and letting $k\to\infty$ to inequality
(3.11) gives the following result

$\displaystyle\mathbb{P}_{\pi}\left(\frac{1}{t}\int_{0}^{t}g\left(X_{s}\right)\mathrm{d}s-\pi(g)\geq\varepsilon\right)$
$\displaystyle=$
$\displaystyle\mathbb{P}_{\pi}\left(\lim_{k\to\infty}\frac{1}{k}\sum_{i=0}^{k-1}g\left(X_{it/k}\right)-\pi(g)\geq\varepsilon\right)$
$\displaystyle\leq$
$\displaystyle\mathop{\liminf}\limits_{k\to\infty}\mathbb{P}_{\pi}\left(\frac{1}{k}\sum_{i=0}^{k-1}g\left(X_{it/k}\right)-\pi(g)\geq\varepsilon\right)$
$\displaystyle\leq$
$\displaystyle\mathop{\liminf}\limits_{k\to\infty}\exp\left\\{-2\cdot\frac{t{\lambda}(Q)-k\cdot
o(\frac{1}{k})}{2-\frac{t}{k}{\lambda}(Q)+o(\frac{1}{k})}\cdot\frac{\varepsilon^{2}}{(b-a)^{2}}\right\\}$
$\displaystyle=$
$\displaystyle\exp\left\\{\lim_{k\to\infty}-2\cdot\frac{t{\lambda}(Q)-k\cdot
o(\frac{1}{k})}{2-\frac{t}{k}{\lambda}(Q)+o(\frac{1}{k})}\cdot\frac{\varepsilon^{2}}{(b-a)^{2}}\right\\}$
$\displaystyle=$
$\displaystyle\exp\left\\{-\frac{{\lambda}(Q)t\varepsilon^{2}}{(b-a)^{2}}\right\\}.$

Thus, we obtain the assertion. ∎

Using the same proof of Theorem 3.2, we can obtain the Hoeffding inequality
for a infinite state CTMC with a uniformly bounded $Q$-matrix (i.e.,
$\sup_{i\in E}-Q(i,i)<\infty$).

######  Corollary 3.1.

Assume that the chain $X_{t}$ admits an $\mathcal{L}^{2}(\pi)$-spectral gap
$\lambda(Q)$, and that the $Q$-matrix $Q$ is uniformly bounded. Then for any
bounded function $g:E\to[a,b]$, and $t,\varepsilon>0$, we have

$\mathbb{P}_{\pi}\left(\frac{1}{t}\int_{0}^{t}g\left(X_{s}\right)\mathrm{d}s-\pi(g)\geq\varepsilon\right)\leq\exp\left\\{-\frac{\lambda(Q)t\varepsilon^{2}}{(b-a)^{2}}\right\\}.$

However, since equality (3.3) fails to hold for a CTMC with an unbounded
$Q$-matrix, the skeleton chain technique is not applicable to more general
CTMCs, which urges us to develop the augmented truncation approximation
technique in order to extend the results from finite state CTMCs to infinite
state CTMCs.

###  3.2 The collapsed chain

We first introduce the technique of the collapsed chain, one special augmented
truncation approximation. Let $\\{{}_{(n)}E,n=1,2,\ldots\\}$ be a sequence of
subsets in the state space $E$, satisfying ${}_{(n)}E\subset{}_{(n+1)}E$ and
$\lim_{n\rightarrow\infty}{}_{(n)}E=E$. Then, let ${}_{(n)}E^{C}$ be the
complement of ${}_{(n)}E$ and consider ${}_{(n)}e={}_{(n)}E^{C}$ as a new
single-point state. For an irreducible and regular $Q$-matrix
$Q=(Q(i,j))_{i,j\in{E}}$, consider the augmented truncation $Q$-matrix
${}_{(n+1)}\widetilde{Q}=({}_{(n+1)}\widetilde{Q}(i,j))_{i,j\in{{}_{(n+1)}\widetilde{E}}}$
on the state space ${}_{(n+1)}\widetilde{E}={}_{(n)}E\cup\\{{{}_{(n)}e}\\}$,
given by

${}_{(n+1)}\widetilde{Q}(i,j)=Q(i,j),\ \ i,j\in{{}_{(n)}E},$
${}_{(n+1)}\widetilde{Q}(i,{{}_{(n)}e})=\sum_{k\in{{}_{(n)}E^{C}}}Q(i,k),\ \
i\in{{}_{(n)}E},$
${}_{(n+1)}\widetilde{Q}({{}_{(n)}e},i)=\frac{\sum_{k\in{{}_{(n)}E^{C}}}\pi(k)Q(k,i)}{\sum_{k\in{{}_{(n)}E^{C}}}\pi(k)},\
\ i\in{{}_{(n)}E},$

and

${}_{(n+1)}\widetilde{Q}({{}_{(n)}e},{{}_{(n)}e})=-\sum_{k\in{{}_{(n)}E}}{}_{(n+1)}\widetilde{Q}({{}_{(n)}e},k).$

Denote by $\big{\\{}{}_{(n+1)}\widetilde{X}_{t},t\geq 0\big{\\}}$ the CTMC
with $Q$-matrix ${}_{(n+1)}\widetilde{Q}$, whose irreducibility is inherent
from the irreducibility of the original chain. The chain
${}_{(n+1)}\widetilde{X}_{t}$ is called the collapsed chain since it can be
interpreted as “the original chains with states collapsed to a single state
${{}_{(n)}e}$”. This collapsed chain was essentially introduced in Chapter 9
of [14] for continuous-time reversible Markov chains. Here we do not need the
reversibility assumption. The discrete-time version of the collapsed chain was
introduced in Chapter 2 of [2]. Let
${}_{(n+1)}\widetilde{\pi}(i)=\pi(i),i\in{{}_{(n)}E},{}_{(n+1)}\tilde{\pi}({{}_{(n)}e})=\sum_{k\in{{}_{(n)}E^{C}}}\pi(k)$.
It is not difficult to verify that ${}_{(n+1)}\widetilde{\pi}$ is the unique
stationary distribution of the chain ${}_{(n+1)}\widetilde{X}_{t}$.

Let ${{}_{(n+1)}\widetilde{g}}$ be an $(n+1)$-dimensional function on
${{}_{(n+1)}\widetilde{E}}$, such that ${}_{(n+1)}\widetilde{g}(i)=g(i)$,
$i\in{{}_{(n)}E}$ and ${}_{(n+1)}\widetilde{g}({{}_{(n)}e})=0$. For the chain
${{}_{(n)}\widetilde{X}_{t}}$ and the function ${}_{(n)}\widetilde{g}$, we
have the following lemma.

######  Lemma 3.1.

For any bounded function $g$ on $E$, we have

$\mathbb{P}_{i}\left(\omega\in\varOmega:\lim_{n\rightarrow\infty}{{}_{(n)}\widetilde{g}}\big{(}{}_{(n)}\widetilde{X}_{s}(\omega)\big{)}=g\left(X_{s}(\omega)\right)\right)=1,$

and

$\lim_{n\rightarrow\infty}{}_{(n)}\widetilde{\pi}\left({}_{(n)}\widetilde{g}\right)=\pi(g).$

###### Proof.

Since $Q$-matrix $Q$ is regular, we know that the chain $X_{t}$ is non-
explosive, i.e., for any fixes $s>0$,

$\mathbb{P}_{i}\left(\omega\in\Omega:J(s,\omega)<\infty\right)=1,$

where $J(s)$ denotes the number of jumps of $X_{t}$ in the time interval
$(0,s)$. Furthermore, for any sample path $\omega$, we define $M_{s}(\omega)$
as a subset of $E$ that includes all states visited by $X_{t}(\omega)$ during
the time interval $(0,s)$. Hence, we can find an $N$ such that
$M_{s}(\omega)\subset{{}_{(n)}E}$ for all $n>N$. Due to the particular
structure of ${}_{(n)}\widetilde{Q}$, we have
${}_{(n)}\widetilde{X}_{t}(\omega)=X_{t}(\omega),0\leq t\leq s$, $n>N$. That
is, for any fixed $s>0$,

$\mathbb{P}_{i}\left(\omega\in\Omega:\lim_{n\rightarrow\infty}{}_{(n)}\widetilde{X}_{s}(\omega)=X_{s}(\omega)\right)=1.$

Furthermore, for any bounded function $g$ on $E$, we have

$\mathbb{P}_{i}\left(\omega\in\Omega:\lim_{n\rightarrow\infty}{{}_{(n)}\widetilde{g}}\big{(}{}_{(n)}\widetilde{X}_{s}\left(\omega\right)\big{)}=g\left(X_{s}\left(\omega\right)\right)\right)=1.$

On the other hand, by applying the dominated convergence theorem, we can
conclude that

$\begin{split}\lim_{n\rightarrow\infty}{}_{(n)}\widetilde{\pi}\left({}_{(n)}\widetilde{g}\right)&=\lim_{n\rightarrow\infty}\sum_{i\in{{}_{(n-1)}E}}\pi(i)g(i)\\\
&=\lim_{n\rightarrow\infty}\sum_{i\in{E}}\pi(i){g}(i)\mathbf{1}_{\\{i\in{{{}_{(n-1)}\widetilde{E}}}\\}}\\\
&=\pi(g),\end{split}$

where $\mathbf{1}_{\\{\cdot\\}}$ is the indicator function. Thus, we complete
the proof of this lemma. ∎

######  Lemma 3.2.

Assume that the original chain $X_{t}$ admits an
$\mathcal{L}^{2}(\pi)$-spectral gap $\lambda(Q)$, and that the $Q$-matrix
$\bar{Q}$ is regular. Then we have

$\lim_{n\rightarrow\infty}{\lambda}({}_{(n)}\widetilde{Q})={\lambda}(Q).$

###### Proof.

Since $\bar{Q}$ is regular, according to (2.7) and (2.8), we have

$\displaystyle\lambda(D)$ $\displaystyle=$
$\displaystyle\inf\left\\{D^{*}(f):\ \|f\|_{\pi,2}=1,\ \pi(f)=0\right\\}$
(3.12) $\displaystyle=$ $\displaystyle\inf\left\\{D^{*}(f):f\in\mathcal{K},\
\|f\|_{\pi,2}=1,\ \pi(f)=0\right\\},$

where $\mathcal{K}$ is the set of all functions on $E$ with finite support.
Without loss of generality, support that $f(i)=d$, $i\in{{}_{(n-1)}E^{C}}$,
for some $n>1$, where $d$ is a constant. The rest of the proof is modified
from the proof of Theorem 9.20 in [14]. It is simple to show that $\pi(f)=0$,
$\|f\|_{\pi,2}=1$ if and only if ${}_{(n)}\widetilde{\pi}({{}_{(n)}{f}})=0$,
$\|{{}_{(n)}{f}}\|_{{}_{(n)}\widetilde{\pi},2}=1$. Now, let

${}_{(n)}{D}^{\ast}({f})=\frac{1}{2}\sum_{i,j\in{{}_{(n)}E}}{}_{(n)}\widetilde{\pi}(i){}_{(n)}{\widetilde{Q}}(i,j)(f(i)-f(j))^{2},\
\ \forall f\in{\mathcal{L}^{2}({}_{(n)}\widetilde{\pi})}.$

Furthermore, we have

$\displaystyle{D}^{\ast}(f)$ $\displaystyle=$
$\displaystyle\frac{1}{2}\sum_{i,j\in
E}\pi(i){Q}(i,j)\left(f(j)-f(i)\right)^{2}$ $\displaystyle=$
$\displaystyle\frac{1}{2}\sum_{i\in{}_{(n-1)}E}\pi(i)\sum_{j\in{}_{(n-1)}E}{Q}(i,j)\left(f(j)-f(i)\right)^{2}+\frac{1}{2}\sum_{i\in{}_{(n-1)}E}\pi(i)\sum_{j\in{}_{(n-1)}E^{c}}{Q}(i,j)\left(d-f(i)\right)^{2}$
$\displaystyle+\frac{1}{2}\sum_{i\in{}_{(n-1)}E^{C}}\pi(i)\sum_{j\in{}_{(n-1)}E}{Q}(i,j)\left(d-f(j)\right)^{2}$
$\displaystyle=$
$\displaystyle\frac{1}{2}\sum_{i\in{}_{(n-1)}E}{}_{(n)}\widetilde{\pi}(i)\sum_{j\in{}_{(n-1)}E}{}_{(n)}{\widetilde{Q}}(i,j)\left(f(j)-f(i)\right)^{2}+\frac{1}{2}\sum_{i\in{}_{(n-1)}E}{}_{(n)}\widetilde{\pi}(i){}_{(n)}{\widetilde{Q}}(i,n)\left(d-f(i)\right)^{2}$
$\displaystyle+\frac{1}{2}\sum_{i\in{}_{(n-1)}E}{}_{(n)}\tilde{\pi}(n){}_{(n)}{\widetilde{Q}}(n,i)\left(d-f(i)\right)^{2}$
$\displaystyle=$
$\displaystyle\frac{1}{2}\sum_{i\in{}_{(n)}E}{}_{(n)}\widetilde{\pi}(i)\sum_{j\in{}_{(n)}E}{}_{(n)}{\widetilde{Q}}(i,j)\left({}_{(n)}{f}(j)-{}_{(n)}{f}(i)\right)^{2}$
$\displaystyle=$ $\displaystyle{}_{(n)}{D}^{\ast}({{}_{(n)}{f}}).$

From $(\ref{nd-1})$ and the above equation, we know that

$\displaystyle{\lambda}({Q})$ $\displaystyle=$
$\displaystyle\inf\left\\{{D}^{\ast}(f):\pi(f)=0,\|f\|_{\pi,2}=1,f(i)=d\
\text{for}\ i\in{{}_{(n-1)}E^{C}}\ \text{and some}\ n>1\right\\}$ (3.13)
$\displaystyle=$
$\displaystyle\lim_{n\rightarrow\infty}\inf\left\\{{D}^{\ast}(f):\pi(f)=0,\|f\|_{\pi,2}=1,f(i)=d\
\text{for}\ i\in{{}_{(n-1)}E^{C}}\ \text{and some}\ n>1\right\\}$
$\displaystyle=$
$\displaystyle\lim_{n\rightarrow\infty}\inf\left\\{{}_{(n)}{D}^{\ast}({{}_{(n)}{f}}):{}_{(n)}\widetilde{\pi}({{}_{(n)}f})=0,\|{{}_{(n)}f}\|_{{{}_{(n)}\widetilde{\pi}},2}=1\right\\}$
$\displaystyle=$
$\displaystyle\lim_{n\rightarrow\infty}{\lambda}({}_{(n)}\widetilde{Q}).$

Thus, combining with (2.7) and (3.13), we obtain the assertion immediately. ∎

###  3.3 Infinite state CTMCs

We now finish the proof of Theorem 2.1 by extending Hoeffding’s inequality
from finite state CTMCs to infinite state CTMCs.

###### Proof of Theorem 2.1.

According to Theorem 3.2, for any bounded function $g:E\to[a,b]$ and $n\geq
1$, we have

$\mathbb{P}_{{}_{(n)}\widetilde{\pi}}\left(\frac{1}{t}\int_{0}^{t}{{}_{(n)}\widetilde{g}}\left({}_{(n)}\widetilde{X}_{s}\right)\mathrm{d}s-{}_{(n)}\pi({{}_{(n)}\widetilde{g}})\geq\varepsilon\right)\leq\exp\left\\{-\frac{{\lambda}({}_{(n)}\widetilde{Q})t}{(b-a)^{2}}\varepsilon^{2}\right\\}.$
(3.14)

Then, applying Lemmas 3.1-3.2 and Fatou’s Lemma, and letting $n\to\infty$ to
inequality (3.14), we have

$\displaystyle\mathbb{P}_{\pi}\left(\frac{1}{t}\int_{0}^{t}g\left(X_{s}\right)\mathrm{d}s-\pi(g)\geq\varepsilon\right)$
$\displaystyle=$
$\displaystyle\sum_{i\in{E}}\pi(i)\mathbb{P}_{i}\left(\frac{1}{t}\int_{0}^{t}g\left(X_{s}\right)\mathrm{d}s-\pi(g)\geq\varepsilon\right)$
$\displaystyle=$
$\displaystyle\sum_{i\in{E}}\lim_{n\rightarrow\infty}\mathbf{1}_{\\{i\in{{}_{(n)}\widetilde{E}}\\}}{{}_{(n)}\widetilde{\pi}(i)}\mathbb{P}_{i}\left(\frac{1}{t}\int_{0}^{t}\lim_{n\rightarrow\infty}{{}_{(n)}\widetilde{g}}\left({}_{(n)}X_{s}\right)\mathrm{d}s-\lim_{n\rightarrow\infty}{}_{(n)}\pi({{}_{(n)}\widetilde{g}})\geq\varepsilon\right)$
$\displaystyle\leq$
$\displaystyle\liminf_{n\rightarrow\infty}\sum_{i\in{{}_{(n)}\widetilde{E}}}{{}_{(n)}\widetilde{\pi}(i)}\mathbb{P}_{i}\left(\frac{1}{t}\int_{0}^{t}{{}_{(n)}\widetilde{g}}\left({}_{(n)}X_{s}\right)\mathrm{d}s-{}_{(n)}\pi({{}_{(n)}\widetilde{g}})\geq\varepsilon\right)$
$\displaystyle=$
$\displaystyle\liminf_{n\rightarrow\infty}\mathbb{P}_{{}_{(n)}\widetilde{\pi}}\left(\frac{1}{t}\int_{0}^{t}{{}_{(n)}\widetilde{g}}\left({}_{(n)}X_{s}\right)\mathrm{d}s-{}_{(n)}\pi({{}_{(n)}\widetilde{g}})\geq\varepsilon\right)$
$\displaystyle\leq$
$\displaystyle\mathop{\lim\inf}\limits_{n\to\infty}\exp\left\\{-\frac{\lambda({}_{(n)}\widetilde{Q})t\varepsilon^{2}}{(b-a)^{2}}\right\\}$
$\displaystyle=$
$\displaystyle\exp\left\\{\lim_{n\rightarrow\infty}-\frac{\lambda({}_{(n)}\widetilde{Q})t\varepsilon^{2}}{(b-a)^{2}}\right\\}$
$\displaystyle=$
$\displaystyle\exp\left\\{-\frac{{\lambda}(Q)t\varepsilon^{2}}{(b-a)^{2}}\right\\}.$

∎

##  4 Extensions to Jump Processes

In this section, let $E$ be a general state space and $\mathcal{B}$ represent
the associated $\sigma$-algebra. Let $\\{X_{t},t\geq 0\\}$ be an irreducible
time-homogeneous continuous-time Markov process on $E$ with the transition
function $P_{t}=(P_{t}(x,A))_{x\in{E},A\in{\mathcal{B}}}$ and the stationary
distribution $\pi$. We assume that $P_{t}$ is continuous at the origin, i.e.,
$X_{t}$ is a jump process. Please refer to [14] for more details about jump
processes. Furthermore, we focus on the case that $X_{t}$ has a $q$-pair
$(q(x),q(x,A))$, i.e., for any $x\in{E}$, $A\in\mathcal{B}$, we have

$\lim_{t\rightarrow
0}\frac{P_{t}(x,A)-\mathbf{1}_{\\{x\in{A}\\}}}{t}=q(x,A)-q(x)\mathbf{1}_{\\{x\in{A}\\}},\
\ x\in{E},A\in\mathcal{B}.$

Furthermore, we assume that this $q$-pair $(q(x),q(x,A))$ is totally stable,
conservative and regular. The infinitesimal generator $\mathcal{A}$ generated
by $P_{t}$ is defined by (2.1). We define

$\lambda(q):=\inf\left\\{-\langle{\mathcal{A}}f,f\rangle_{\pi}:f\in\mathcal{D}({\mathcal{A}}),\
\|f\|_{\pi,2}=1,\ \pi(f)=0\right\\},$

where $\mathcal{D}(\mathcal{A})$ is the domain of $\mathcal{A}$. If
$\lambda(q)>0$, $\lambda(q)$ is said to be the $\mathcal{L}^{2}(\pi)$-spectral
gap of $X_{t}$.

By the technique of skeleton chains, we can obtain the following result
similar to Corollary 3.1.

######  Lemma 4.1.

Assume that the process $X_{t}$ exists an $\mathcal{L}^{2}(\pi)$-spectral gap
$\lambda(q)$, and that the $q$-pair $(q(x),q(x,A))$ is uniformly bounded. Then
for any bounded continuous function $g:E\to[a,b]$, and $t,\varepsilon>0$, we
have

$\mathbb{P}_{\pi}\left(\frac{1}{t}\int_{0}^{t}g\left(X_{s}\right)\mathrm{d}s-\pi(g)\geq\varepsilon\right)\leq\exp\left\\{-\frac{\lambda(q)t\varepsilon^{2}}{(b-a)^{2}}\right\\}.$

Similar to the case of countable state space, define

$D^{*}(f):=\frac{1}{2}\int_{x,y\in{E}}\pi(dx)q(x,dy)\left(f(x)-f(y)\right)^{2},\
\ \forall{f}\in\mathcal{L}^{2}(\pi),$

and

$\mathcal{D}(D^{*}):=\left\\{f\in\mathcal{L}^{2}(\pi):D^{*}(f)<\infty\right\\},$

where $\mathcal{D}(D^{*})$ is the domain of $D^{*}$. Let $\mathcal{K}$ be the
set of all functions on $E$ with finite support. According to Theorem 9.11 in
[14], we know that if $\mathcal{K}$ is dense in $D^{*}$, then

$\lambda(q)=\inf\left\\{D^{*}(f):f\in\mathcal{K},\ \|f\|_{\pi,2}=1,\
\pi(f)=0\right\\}.$

Now, let $\\{{}_{(n)}E,n=1,2,\ldots\\}$ be an increasing sequence compact
subsets of $E$ such that

$\int_{{}_{(n)}E^{C}}\pi(dx)>0,\ \ n\geq 1.$

Furthermore, let ${}_{(n)}e={}_{(n)}E^{C}$ as a new single-point state. We
consider the following collapsed $q$-pair
$({{}_{(n+1)}\widetilde{q}},{{}_{(n+1)}\widetilde{q}(x,A)})$ on
${}_{(n+1)}\widetilde{E}={}_{(n)}E\cup\\{{{}_{(n)}e}\\}$, which is given by

${}_{(n+1)}\widetilde{q}(x,A)=q(x,A\cap{{}_{(n)}E})+\mathbf{1}_{\\{{{}_{(n)}e}\in{A}\\}}q(x,{{}_{(n)}E^{C}}),\
\ x\in{{{}_{(n)}E}},A\in{{}_{(n+1)}\mathcal{B}},$
${}_{(n+1)}\widetilde{q}({{}_{(n)}e},A)=\frac{\int_{{{}_{(n)}E^{C}}}\pi(dx)q(x,A\cap{{}_{(n)}E})}{\int_{{}_{(n)}E^{C}}\pi(dx)},\
\ A\in{{}_{(n+1)}\mathcal{B}},$

and

${}_{(n+1)}\widetilde{q}(x)={}_{(n+1)}\widetilde{q}(x,{}_{(n+1)}\widetilde{E}),\
\ x\in{{{}_{(n)}E}},$

where ${{}_{(n+1)}\mathcal{B}}$ is the $\sigma$-algebra generated by
${{{}_{(n+1)}\widetilde{E}}}$. Then, let
$\big{\\{}{}_{(n+1)}\widetilde{X}_{t},t\geq 0\big{\\}}$ be the jump process on
${}_{(n+1)}\widetilde{E}$ corresponding to the $q$-pair
$({{}_{(n+1)}\widetilde{q}},{{}_{(n+1)}\widetilde{q}(x,A)})$, and
${}_{(n+1)}\widetilde{\pi}$ be the stationary distribution of
${}_{(n+1)}\widetilde{X}_{t}$ such that
${}_{(n+1)}\widetilde{\pi}(A)=\int_{A\cap{{}_{(n)}E}}\pi(dx)$ for
${{}_{(n)}e}\notin{A}$ and
${}_{(n+1)}\widetilde{\pi}(A)=\int_{A\cap{{}_{(n)}E}}\pi(dx)+\int_{{}_{(n)}E^{C}}\pi(dx)$
for ${{}_{(n)}e}\in{A}$. Finally, let ${{}_{(n+1)}\widetilde{g}}$ be a
continuous truncation function satisfying ${}_{(n+1)}\widetilde{g}(x)=g(x)$
for $x\in{{}_{(n)}E}$ and ${}_{(n+1)}\widetilde{g}({{}_{(n)}e})=0$.

By following a similar proof technique as in Lemma 3.1 and 3.2, we obtain the
following convergence result.

######  Lemma 4.2.

For the collapsed process ${}_{(n)}\widetilde{X}_{t}$, we have that

(i)

if $g$ is a bounded continuous function on $E$, then

$\mathbb{P}_{i}\left(\omega\in\varOmega:\lim_{n\rightarrow\infty}{{}_{(n)}\widetilde{g}}\big{(}{}_{(n)}\widetilde{X}_{s}(\omega)\big{)}=g\left(X_{s}(\omega)\right)\right)=1,$

and

$\lim_{n\rightarrow\infty}{}_{(n)}\widetilde{\pi}\left({}_{(n)}\widetilde{g}\right)=\pi(g);$

(ii)

and if the original process $X_{t}$ admits an $\mathcal{L}^{2}(\pi)$-spectral
gap $\lambda(q)$, and $\mathcal{K}$ is dense in $D^{*}$, then

$\lim_{n\rightarrow\infty}{\lambda}({}_{(n)}\widetilde{q})={\lambda}(q).$

By combining Lemmas 4.1 and 4.2, and using a similar argument in the proof of
Theorem 2.1, we obtain the following Hoeffding’s inequality for a jump process
on a general state space.

######  Theorem 4.1.

Assume that the process $X_{t}$ exists an $\mathcal{L}^{2}(\pi)$-spectral gap
$\lambda(q)$, and that $\mathcal{K}$ is dense in $D^{*}$. Then for any bounded
continuous function $g:E\to[a,b]$, and $t,\varepsilon>0$, we have

$\mathbb{P}_{\pi}\left(\frac{1}{t}\int_{0}^{t}g\left(X_{s}\right)\mathrm{d}s-\pi(g)\geq\varepsilon\right)\leq\exp\left\\{-\frac{\lambda(q)t\varepsilon^{2}}{(b-a)^{2}}\right\\}.$

## References

  * [1] Adamczak, R. and Bednorz, W. (2012). Exponential concentration inequalities for additive functionals of Markov chains.  ESAIM Probab. Stat. 19 440–481.
  * [2] Aldous, D. and Fill, J. A. (2014). Reversible Markov Chains and Random Walks on Graphs. https://www.stat.berkeley.edu/users/aldous/.
  * [3] Anderson, W. J. (1991). Continuous-time Markov Chains: An Applications-Oriented Approach. Springer-Verlag, New York.
  * [4] Baddeley, A. J. (2000). Time-invariance estimating equations. Bernoulli 6 783–808.
  * [5] Bai, Z. and Lin, Z. (2009). Probability Inequalities. Science Press, Beijing.
  * [6] Bierkens, J., Bouchard-Côté, A., Doucet, A., Duncan, A. B., Fearnhead, P., Lienart, T., Roberts, G. and Vollmer, S. J. (2018). Piecewise deterministic Markov processes for scalable Monte Carlo on restricted domains. Statist. Probab. Lett. 136 148–154.
  * [7] Bouchard-Côté, A., Vollmer, S. J. and Doucet, A. (2018). The bouncy particle sampler: A nonreversible rejection-free Markov chain Monte Carlo method. J. Amer. Statist. Assoc. 113 855–867.
  * [8] Boucher, T. R. (2009). A Hoeffding inequality for Markov chains using a generalized inverse. Statist. Probab. Lett. 79 1105–1107.
  * [9] Boucheron, S., Lugosi, G. and Massart, P. (2013). Concentration Inequalities: A Nonasymptotic Theory of Independence. Oxford University Press, Oxford.
  * [10] Bubeck, S. and Cesa-Bianchi, N. (2012). Regret analysis of stochastic and nonstochastic multi-armed bandit problems. Found. Trends Mach. Learn. 5 1–122.
  * [11] Cai, T. T., Zhang, C.-H. and Zhou, H. H. (2010). Optimal rates of convergence for covariance matrix estimation. Ann. Statist. 38 2118–2144.
  * [12] Chatterjee, S. (2007). Stein’s method for concentration inequalities. Probab. Theory Related Fields 138 305–321.
  * [13] Chen, M. (2000). Equivalence of exponential ergodicity and L2-exponential convergence for Markov chains. Stochastic Process. Appl. 87 281–297.
  * [14] Chen, M. (2004). From Markov Chains to Non-Equilibrium Particle Systems, 2nd ed. World Scientific, Singapore.
  * [15] Chen, M. (2010). Speed of stability for birth-death processes. Front. Math. China 5 379–515.
  * [16] Choi, M. C. H. and Li, E. (2019). A Hoeffding’s inequality for uniformly ergodic diffusion process. Statist. Probab. Lett. 150 23–28.
  * [17] Dedecker, J. and Gouëzel, S. (2014). Subgaussian concentration inequalities for geometrically ergodic Markov chains. Electron. Commun. Probab. 20 1–12.
  * [18] Devroye, L., Györfi, L. and Lugosi, G. (1996). A Probabilistic Theory of Pattern Recognition. Springer-Verlag, New York.
  * [19] Dinwoodie, I. H. (1995). A probability inequality for the occupation measure of a reversible Markov chain. Ann. Appl. Probab. 5 37–43.
  * [20] Fan, J., Jiang, B. and Sun, Q. (2021). Hoeffding’s inequality for general Markov chains and its applications to statistical learning. J. Mach. Learn. Res. 22 6185–6219.
  * [21] Fearnhead, P., Bierkens, J., Pollock, M. and Roberts, G. O. (2018). Piecewise deterministic Markov processes for continuous-time Monte Carlo. Statist. Sci. 33 386–412.
  * [22] Gillman, D. W. (1993). Hidden Markov chains: convergence rates and the complexity of inference. Massachusetts Institute of Technology.
  * [23] Glynn, P. W. and Ormoneit, D. (2002). Hoeffding’s inequality for uniformly ergodic Markov chains. Statist. Probab. Lett. 56 143–146.
  * [24] Granovsky, B. L. and Zeifman, A. I. (1997). The decay function of nonhomogeneous birth-death processes, with application to mean-field models. Stochastic Process. Appl. 72 105–120.
  * [25] Guillin, A., Léonard, C., Wu, L. and Yao, N. (2009). Transportation-information inequalities for Markov processes. Probab. Theory Related Fields 144 669–695.
  * [26] Hoeffding, W. (1963). Probability inequalities for sums of bounded random variables. J. Amer. Statist. Assoc. 58 13–30.
  * [27] Jarner, S. F. and Tweedie, R. L. (2002). Convergence rates and moments of Markov chains associated with the mean of Dirichlet processes. Stochastic Process. Appl. 101 257–271.
  * [28] León, C. A. and Perron, F. (2004). Optimal Hoeffding bounds for discrete reversible Markov chains. Ann. Appl. Probab. 14 958–970.
  * [29] Lezaud, P. (2001). Chernoff and Berry-Esséen inequalities for Markov processes. ESAIM Probab. Stat. 5 183–201.
  * [30] Lézaud, P. (1998). Chernoff-type bound for finite Markov chains. Ann. Appl. Probab. 8 849–867.
  * [31] Liu, Y. and Liu, J. (2021). Hoeffding’s inequality for Markov processes via solution of Poisson’s equation. Front. Math. China 16 543–558.
  * [32] Miasojedow, B. (2014). Hoeffding’s inequalities for geometrically ergodic Markov chains on general state space. Statist. Probab. Lett. 87 115–120.
  * [33] Paulin, D. (2015). Concentration inequalities for Markov chains by Marton couplings and spectral methods. Electron. J. Probab. 20 1–32.
  * [34] Roberts, G. O. and Tweedie, R. L. (1996). Geometric convergence and central limit theorems for multidimensional Hastings and Metropolis algorithms. Biometrika 83 95–110.
  * [35] Wang, N.-Y. and Wu, L. (2020). Transport-information inequalities for Markov chains.  Ann. Appl. Probab. 30 1276–1320.
  * [36] Wintenberger, O. (2017). Exponential inequalities for unbounded functions of geometrically ergodic Markov chains: applications to quantitative error bounds for regenerative Metropolis algorithms. Statistics 51 222–234.
  * [37] Yuan, M. and Kendziorski, C. (2006). Hidden Markov models for microarray time course data in multiple biological conditions. J. Amer. Statist. Assoc. 101 1323–1332.


# Disorder-dependent slopes of the upper critical field in nodal and nodeless
superconductors

V. G. Kogan<EMAIL_ADDRESS>Ames National Laboratory, Ames, Iowa 50011,
U.S.A.  R. Prozorov<EMAIL_ADDRESS>Ames National Laboratory, Ames, Iowa
50011, U.S.A.  Department of Physics & Astronomy, Iowa State University, Ames,
IA 50011, U.S.A.

###### Abstract

We study the slopes of the upper critical field
$\partial_{T}H_{c2}|_{T_{c}}\equiv\partial H_{{}_{c2}}/\partial T$ at $T_{c}$
in anisotropic superconductors with transport (non-magnetic) scattering
employing the Ginzburg-Landau theory, developed for this situation by S.
Pokrovsky and V. Pokrovsky, Phys. Rev. B, 54, 13275 (1996). We found
unexpected behavior of the slopes for a $d-$wave superconductor and in a more
general case of materials with line nodes in the order parameter.
Specifically, the presence of line nodes causes $\partial_{T}H_{c2}|_{T_{c}}$
to _decrease_ with increasing non-magnetic scattering parameter $P$, unlike
the nodeless case where the slope _increases_. In a pure $d-$wave case, the
slope $\partial H_{c2}|_{T_{c}}$ changes from decreasing to increasing when
scattering parameter approaches $P\approx 0.91\,P_{{\rm crit}}$, where
$P_{{\rm crit}}\approx 0.2807$ at which $T_{c}\to 0$ that implies the the
existence of a gapless state in $d-$wave superconductors with transport
scattering in the interval, $0.91\,P_{{\rm{crit}}}<P<P_{{\rm crit}}$.
Furthermore, we have considered the mixed $s+d$ order parameter that has 4
nodes on a cylindrical Fermi surface when a $d-$part is dominant, or no nodes
at all when an $s-$phase is the major one. We find that presence of nodes
causes the slope $\partial_{T}H_{c2}|_{T_{c}},$ to decrease initially with
increasing $P$, whereas in the nodeless state, $\partial_{T}H_{c2}|_{T_{c}}$
monotonically increases. Therefore, fairly straightforward experiments make it
possible to decide whether or not the order parameter of a superconductor has
nodes by measuring the disorder-dependence of the slope of $H_{c2}$ at
$T_{c}$.

##  I Introduction

A brief survey of the literature finds many reports on the upper critical
field slope at $T_{c}$ as a function of disorder in various materials. The
consistent picture emerges - superconductors with line nodes show decreasing
slope whereas those without nodes show increasing $\partial H_{c2}/\partial T$
with increasing disorder. For example, the increase was experimentally
observed in fully gapped $s_{\pm}$ iron-based superconductors where
nonmagnetic disorder was introduced by ball-milling [1], irradiation with 2.5
MeV electrons [2] or fast neutrons [3]. On the other hand, a decrease of the
slope concomitant with the decrease of $T_{c}$ was found in a nodal pnictide
superconductor [4].

The problem of slopes $S=\partial H_{c2}/\partial T$ at $T_{c}$ (we also write
it as, $\partial_{T}H_{c2}|_{T_{c}}$) can be addressed with the help of
Ginzburg-Landau (GL) theory. To provide a reasonable theoretical guidance, the
theory should be applicable to various order parameter symmetries and to
anisotropic Fermi surfaces. There were a few attempts to develop such a
version of GL, e.g. [5, 6] have confirmed major features of the experimental
information on slopes dependence on disorder for superconductors with nodes
and without. However, some recent findings [7] of non-monotonic disorder
dependence of the slopes are puzzling. In this work we employ a most general
version of the GL theory applicable to anisotropic order parameters in the
presence of transport scattering due to S. Pokrovsky and V. Pokrovsky, [8].

Below, we first outline the theory, then we apply it to the d-wave symmetry of
the order parameter and show that, in fact, the slopes $S$ are indeed
suppressed by a relatively weak disorder but increase when the impurity
scattering approaches the critical value at which $T_{c}=0$. Next, we consider
the order parameter which is a superposition of $s$ and $d$ that allows us to
study slopes $S$ in cases of nodes present or not and show that the nodes
change $S(P)$ from the node-free increase to decrease. We end up with a short
discussion of existing and possible experiments.

To simplify the formalism, the effective coupling is commonly assumed
factorizable [9],
$V({\bm{k}},{\bm{k}}^{\prime})=V_{0}\,\Omega({\bm{k}})\,\Omega({\bm{k}}^{\prime})$,
$\bm{k}$ is the Fermi momentum. One then looks for the order parameter in the
form:

$\Delta({\bm{r}},T;{\bm{k}})=\Psi({\bm{r}},T)\,\Omega({\bm{k}})\,.$ (1)

The factor $\Omega({\bm{k}})$ for the order parameter change along the Fermi
surface is conveniently normalized:

$\langle\Omega^{2}\rangle=1\,,$ (2)

where $\langle...\rangle$ stand for the Fermi surface average. This
normalization corresponds to the critical temperature $T_{c0}$ of a clean
material given by the standard isotropic weak-coupling model with the
effective interaction $V_{0}$.

The slope of the upper critical field $H_{c2}$ at $T_{c}$ is determined by the
$T$-dependence of the coherence length $\xi=\xi_{GL}/\sqrt{1-T/T_{c}}$:

$\displaystyle\frac{\partial H_{c2}}{\partial
T}\Big{|}_{T_{c}}=-\frac{\phi_{0}}{2\pi\xi_{GL}^{2}T_{c}}\,.$ (3)

The length $\xi_{GL}$ is of the order of the BCS coherence length
$\xi_{0}=\hbar v_{F}/\pi\Delta(0)$, but differs from $\xi_{0}$, actually it
depends on the coupling, on the impurity scattering, on the order parameter
symmetry, and the Fermi surface anisotropy. All these dependencies can, in
principle, be found within the microscopic BCS theory. This has been done at
early stages of the theory of superconductivity for anisotropic order
parameter only in the clean limit by Gor’kov and Melik-Barkhudarov [9],

$(\xi_{GL}^{2})_{ik}=\frac{7\zeta(3)\hbar^{2}}{16\pi^{2}T_{c}^{2}}\,\langle\Omega^{2}v_{i}v_{k}\rangle\,.$
(4)

The transport scattering was included by Helfand and Werthamer [11] but only
for the isotropic order parameter and Fermi surface:

$\xi_{GL}^{2}=\frac{\hbar^{2}v^{2}}{24\pi^{3}T_{c}^{2}P^{2}}\left[\frac{\pi^{2}P}{4}-\psi\left(\frac{1+P}{2}\right)+\psi\left(\frac{1}{2}\right)\right]\,.$
(5)

Here, $\psi$ is the di-gamma function and the scattering parameter

$P=\hbar/2\pi T_{c0}\tau$ (6)

with $\tau$ being the scattering time and $T_{c0}$ the critical temperature
for clean sample. It is easy to see that the slope
$S=-\partial_{T}H_{c2}|_{T_{c}}$ grows being roughly proportional to $P$. It
is worth paying attention that the material parameter $P$ does not depend on
actual $T_{c}$ unlike the scattering parameter $\rho=\hbar/2\pi T_{c}\tau$
often employed in literature.

The critical temperature of materials with anisotropic order parameter is
suppressed even by non-magnetic impurities. This was established by Openov
[13], see also [14]:

$\displaystyle-\ln\frac{T_{c}}{T_{c0}}=(1-\langle\Omega\rangle^{2})\left[\psi\left(\frac{P/t_{c}+1}{2}\right)-\psi\left(\frac{1}{2}\right)\right],\qquad$
(7)

where $t_{c}=T_{c}/T_{c0}$.

Figure 1: (Color online) $t_{c}=T_{c}/T_{c0}$ vs scattering parameter $P$ for
$\langle\Omega\rangle=0.8,0.5,0.3,0$ in top-down order. Note that for d-wave
$\langle\Omega\rangle=0$ and $T_{c}$ turns zero at the critical scattering
$P_{crit}=1/2e^{\gamma}=0.2807$.

Clearly, $T_{c}=T_{c0}$ for the isotropic order parameter with $\Omega=1$ and
arbitrary scattering rate $P$ as well as for the clean limit and any
anisotropic $\Omega$. For the d-wave $\langle\Omega\rangle=0$ and we have the
standard Abrikosov-Gor’kov result [15] so that the transport scattering in
d-wave affects $T_{c}$ as the pair-breaking scattering in isotropic materials
does.

##  II Linearized Ginzburg-Landau equations

Thus, according to Eq. (3), the slope of $H_{c2}$ at $T_{c}$ is determined by
the coherence length which enters linearized GL equation for the order
parameter $\Psi$,

$-(\xi^{2})_{ik}\Pi_{i}\Pi_{k}\Psi=\Psi$ (8)

with the tensor of squared coherence length $(\xi^{2})_{ik}$;
${\bm{\Pi}}=\nabla+2\pi i{\bm{A}}/\phi_{0}$, $\bm{A}$ is the vector potential
and $\phi_{0}$ is the flux quantum. For arbitrary $\Omega$ and any Fermi
surface in presence of transport scattering, A. Pokrovsky and V. Pokrovsky [8]
evaluated the tensor

$(\xi^{2})_{ik}=\zeta_{ik}/a\,.$ (9)

Here, (in our notation)

$\displaystyle
a=\frac{T_{c}-T}{T_{c}}\left[1+(1-\langle\Omega\rangle^{2})\psi^{\prime}\left(\frac{P/t_{c}+1}{2}\right)\right]\,.$
(10)

The tensor $\hat{\zeta}$ is given by

$\displaystyle\zeta_{ik}$ $\displaystyle=$
$\displaystyle\frac{\hbar^{2}}{16\pi^{2}T_{c}^{2}}\Big{[}h_{3,0}\langle\Omega^{2}v_{i}v_{k}\rangle$
(11) $\displaystyle+$ $\displaystyle\frac{P}{t_{c}}h_{3,1}\langle\Omega
v_{i}v_{k}\rangle\langle\Omega\rangle+\frac{P^{2}}{4t_{c}^{2}}h_{3,2}\langle
v_{i}v_{k}\rangle\langle\Omega\rangle^{2}\Big{]}\,.$

The quantities $h_{\mu,\nu}$ are functions of $x=P/2t_{c}$ defined as

$\displaystyle
h_{\mu,\nu}(x)=\sum_{n=0}^{\infty}(n+1/2+x)^{-\mu}(n+1/2)^{-\nu}\,,$ (12)

so that

$\displaystyle h_{3,0}$ $\displaystyle=$
$\displaystyle-\frac{1}{2}\psi^{\prime\prime}\left(\frac{1}{2}+x\right)\,,$
$\displaystyle h_{3,1}$ $\displaystyle=$
$\displaystyle\frac{1}{x^{3}}\Big{[}\psi\left(\frac{1}{2}+x\right)-\psi\left(\frac{1}{2}\right)-x\psi^{\prime}\left(\frac{1}{2}+x\right)$
$\displaystyle+$
$\displaystyle\frac{x^{2}}{2}\psi^{\prime\prime}\left(\frac{1}{2}+x\right)\Big{]}\,,$
$\displaystyle h_{3,2}$ $\displaystyle=$
$\displaystyle\frac{1}{2x^{4}}\Big{\\{}\pi^{2}x-6\left[\psi\left(\frac{1}{2}+x\right)-\psi\left(\frac{1}{2}\right)\right]$
(13) $\displaystyle+$ $\displaystyle
4x\psi^{\prime}\left(\frac{1}{2}+x\right)-x^{2}\psi^{\prime\prime}\left(\frac{1}{2}+x\right)\Big{\\}}.$

It is straightforward to see that for the isotropic order parameter with
$\Omega=1$ on the Fermi sphere these formulas reduce to the BCS form

$\displaystyle\xi^{2}=\frac{7\zeta(3)}{48\pi^{2}T_{c}^{2}\delta
t}\chi(P)\,,\quad\delta t=1-\frac{T}{T_{c}}\,,$ (14)

with the Gor’kov function

$\displaystyle\chi(P)=\frac{1}{7\zeta(3)}\sum_{n=0}^{\infty}\frac{1}{(n+1/2+P)(n+1/2)^{2}}\,.$
(15)

This limit can also be checked by comparison with $H_{c2}$ slopes at $T_{c}$
given by Helfand and Werthamer [11].

It is worth noting that for the clean limit $x=P/2t_{c}\to 0$, and $h_{3,0}\to
7\zeta(3)$, $h_{3,1}\to\pi^{4}/6$, and $h_{3,2}\to 31\zeta(5)$. This means
that in this limit, only the first term on RHS of Eq. (11) survives in
agreement with [9]. In the opposite limit $x=P/2t_{c}\gg 1$, the last term in
Eq. (11) dominates [8] as is seen in Fig. 2 (however, this limit does not
apply for the d-wave since both the second and the third terms in Eq. (11) are
zeroes due to $\langle\Omega\rangle=0$).

###  II.1 General order parameter

In he general case we obtain for the slope of $H_{c2}$ along the $c$ axis of a
uniaxial material

$\displaystyle\frac{\partial H_{c2}}{\partial
T}\Big{|}_{T_{c}}=-\frac{8\pi\phi_{0}T_{c0}}{\hbar^{2}}\frac{t_{c}\left[1+(1-\langle\Omega\rangle^{2})\psi^{\prime}\left(\frac{1+P/t_{c}}{2}\right)\right]}{h_{3,0}\langle\Omega^{2}v_{a}^{2}\rangle+2(P/2t_{c})h_{3,1}\langle\Omega\rangle\langle\Omega
v_{a}^{2}\rangle+(P/2t_{c})^{2}h_{3,2}\langle\Omega\rangle^{2}\langle
v_{a}^{2}\rangle}\,.\qquad$ (16)

Here, all coefficients $h_{\mu,\nu}(x)$ are taken at $x=P/2t_{c}$.

Figure 2: (Color online) The coefficients $h_{3,0}(x)$, $2xh_{3,1}(x)$, and
$x^{2}h_{3,2}(x)$ vs $x$.

Since the Fermi velocity is not a constant at anisotropic Fermi surfaces, we
normalize velocities on some value $v_{0}$ for which we choose [12]

$v_{0}^{3}=2E_{F}^{2}/\pi^{2}\hbar^{3}N(0)\,,$ (17)

where $E_{F}$ is the Fermi energy and $N(0)$ is the total density of states at
the Fermi level per spin. One easily verifies that $v_{0}=v_{F}$ for the
isotropic case.

The slope expression (16) remains the same except a changed pre-factor

$-\frac{8\pi\phi_{0}T_{c0}}{\hbar^{2}}\to-\frac{8\pi\phi_{0}T_{c0}}{\hbar^{2}v_{0}^{2}}\,,$
(18)

and the velocity $v_{a}$ is now dimensionless (although we leave for it the
same notation).

###  II.2 d-wave

The case of the d-wave symmetry of the order parameter with
$\langle\Omega\rangle=0$ is relatively simple. We have the coherence length
relevant for $H_{c2}$ along $c$ axis of a uniaxial crystal:

$\displaystyle\xi_{aa}^{2}$ $\displaystyle=$
$\displaystyle\frac{\zeta_{aa}}{a}=\frac{\hbar^{2}\langle\Omega^{2}v_{a}^{2}\rangle
h_{3,0}}{16\pi^{2}T_{c}^{2}\left[1+\psi^{\prime}(P/2t_{c}+1/2)\right]\delta
t}.$ (19)

For a Fermi cylinder, with $\Omega=\sqrt{2}\cos 2\varphi$, the average
$\langle\Omega^{2}v_{a}^{2}\rangle=v^{2}/2$. Hence,

$\displaystyle\xi_{aa}^{2}=-\frac{\hbar^{2}v^{2}\,\psi^{\prime\prime}(P/2t_{c}+1/2)}{64\pi^{2}T_{c}^{2}\left[1+\psi^{\prime}(P/2t_{c}+1/2)\right]\delta
t}.$ (20)

and we obtain:

$\displaystyle\frac{dH_{c2,c}}{dT}\Big{|}_{T_{c}}=\frac{32\pi\phi_{0}T_{c0}}{\hbar^{2}v^{2}}\,t_{c}\frac{1+\psi^{\prime}(P/2t_{c}+1/2)}{\psi^{\prime\prime}(P/2t_{c}+1/2)}.$
(21)

For numerical work it is convenient to use the reduced slope

$S=-\frac{dh_{c2}}{dt}\Big{|}_{t_{c}}=-\frac{\hbar^{2}v^{2}}{8\pi\phi_{0}T_{c}}\frac{dH_{c2}}{dT}\Big{|}_{T_{c}}\,.$
(22)

While the actual slope $\left.\partial H_{c2}/\partial T\right|_{T_{c}}$ is
negative, we are interested in its magnitude and use a positive quantity as
given by Eq. (22).

The behavior of the slope as a function of $P$ according to this result is
shown in Fig. 3. As is known, the maximum scattering parameter $P$ for which
the d-wave superconductivity survives is $P_{{\rm{crit}}}=1/2e^{\gamma}=0.28$
(the double of the critical value for the spin-flip magnetic scattering [15]).
Hence, similar to materials with magnetic scatterers [16], the slope $\partial
H_{c2}/\partial T$ at $T_{c}$ for d-wave decreases with increasing transport
scattering. It is worth noting that this behavior changes to increase near
$P\approx 0.91\,P_{{\rm{crit}}}=0.25$; this estimate coincides with that given
by Abrikosov and Gor’kov for the low bound of the gapless state. This suggests
that d-wave materials can also be gapless if the transport scattering
parameter lays in the interval $0.25<P<0.28$. Thus, $S(P)$ dependence might be
a macroscopic manifestation of the gapless superconductivity in impure d-wave
materials, the speculation worth of further study.

Figure 4 shows the slopes of Fig. 3 plotted vs the critical temperate
$t_{c}(P)$.

Figure 3: (Color online) The slope $S=\partial h_{c2}/\partial h$ at $t_{c}$
according to Eq. (22) vs $P$ for a d-wave material. Inset: the same slopes vs
$t_{c}=T_{c}/T_{c0}$.

###  II.3 $\bm{s+d}$

Obviously the major interest in the community is to determine whether the
easily accessible measurements of the $H_{c2}$ slope near $T_{c}$, may provide
some insight into the structure of the order parameter. Here we examine the
simplest case of a $s+d$ state where order parameter is the isotropic s-wave
in one limit and a standard 2D $d-$wave in the other. Keeping in mind the
normalization, $\langle\Omega^{2}\rangle=1,$ a convenient order parameter can
be written as:

$\Omega=\sqrt{1-r^{2}/2}+r\cos(2\varphi)$ (23)

If $r=0$, $\Omega=1$ and when $r=\sqrt{2}$, $\Omega=\sqrt{2}\cos(2\varphi)$
which are the required limiting cases. We choose this order parameter not
because it may describe any particular real material, rather we intend to
check whether or not there is a connection between the microscopic anisotropy
of the order parameter and the macroscopic dependence $S(P)$ of slopes of
$H_{c2}$ on the degree of disorder $P$.

Figure 4: (Color online) $S(P)$ according to Eqs. (22) and (16) for a set of
parameter $r=0,0.75,1,1.2,1.3,1.35,1.4$ and $\sqrt{2}$. The approach to a
gapless regime is characterized by an upturn starting with $P\approx 0.25$ for
a $d$-wave order parameter with $r=\sqrt{2}$. The calculations were performed
for a cylindrical Fermi surface. Figure 5: (Color online) Solid lines are the
slopes $S$ for the same values of the scattering parameters $P$ as in Fig. 4,
but plotted versus the transition temperature $t_{c}(P)$. Dashed continuations
are for $P>0.28$ for which the pure d-wave phase does not exist. In the pure
$s$-wave for which $t_{c}=1$, $S(P)$ does not depend on $P$ and shown by a
vertical red line. Figure 6: (Color online) The rate of change of the slope
$S(P)$ defined as $\chi=S(0.11)-S(0.01))/0.1$, evaluated for different values
of the $r$-coefficient. Nodal behavior starts at $r=\sqrt{2/3}\approx 0.817$.
Apparently, this coincides with the rate of slope change becoming negative.

Figure 4 shows $S(P)$ calculated with the help of Eqs. (16), (22), plotted for
a few coefficients $r$ of the $\Omega$ function, Eq. (23). At $r=0$ the order
parameter is the isotropic $s$-wave, whereas at $r=\sqrt{2}$ it is a two-
dimensional d-wave order parameter. The calculations were performed for a
cylindrical Fermi surface keeping in mind possible applications of this work
to high-$T_{c}$ cuprates. Figure 4 shows that the slopes $S(P)$ for purely
d-wave are (a) non-monotonic and decrease with increasing $P$ up to about
$P=0.25$ following by divergence when $P\to 0.28$, as we have seen in Fig. 3.
With increasing fraction of s-wave, however, the negative slope of $S(P)$ for
small and intermediate $P$ weakens and turns to positive nearly linear
increase of $S$. To gain a further insight, we plot $S(P)$ versus $t_{c}$ in
Fig. 5.

Since the overall behavior of the slopes $S(P)$ depends on fractions of $s$
and $d$ phases, we consider the relative difference
$\chi=S(0.11)-S(0.01))/0.1$ which characterizes this behavior, i.e. increase
for $\chi>0$ and decrease for $\chi<0$. Figure 6 shows this difference plotted
versus coefficient $r$ of the order parameter, Eq. (23). A straightforward
algebra shows that the order parameter is nodeless (anisotropic $s$) for
$r<\sqrt{2/3}\approx 0.82$ and has four line nodes for $r>\sqrt{2/3}$.
Remarkably, Fig. 6 shows that the rate of slope change $\chi$ becomes negative
as soon as the nodes appear. In other words, if one would measure
$\left|S\right|=|\partial H_{c2}/\partial T|_{T_{c}}|$ as a function of non-
magnetic disorder, the increasing $S$ would indicate nodeless
superconductivity, whereas the slope decrease can be considered as evidence
for the nodes presence.

##  III Discussion

We have applied the GL theory developed by S. Pokrovsky and V. Pokrovsky [8]
for anisotropic materials in the presence of non-magnetic scattering to
evaluate slopes $\partial H_{c2}/\partial T|_{T_{c}}$ for d-wave
superconductors and for the case of mixed $s+d$ symmetry. For the d-wave, we
find that for weak and intermediate scattering rates $P=\hbar/2\pi
T_{c0}\tau$, the slopes $S=-\partial H_{c2}/\partial T|_{T_{c}}$ are
suppressed, similar to the situation of the magnetic pair-breaking disorder
and opposite to the transport scattering enhancement of slopes $S(P)$ for the
$s$-wave. One example of such a behavior is in studies of slopes in YBaCuO by
Antonov et al. [17].

Unexpectedly however, if the scattering rate approaches the critical value
$P_{crit}=0.28$ for which $T_{c}\to 0$, the slopes increase starting with
$P\approx 0.25$ to diverge at $P_{crit}$. The value $0.25\approx 0.9$ of
$P_{crit}$, the fraction found by Abrikosov and Gor’kov for the low bound of
the gapless domain in standard $s$-wave materials with magnetic impurities
[15]. This analogy suggests strongly that in d-wave with non-magnetic disorder
close to the maximum disorder possible we are dealing with a kind of “gapless”
state. In our view, this speculation deserves careful examination.

The slopes at $T_{c}$ are the easiest thing one can measure after a new
superconductor is discovered. It has been done in-situ even for room-
temperature materials under extremely high pressures within diamond pressure
cells. If indeed, the easily done macroscopic measurement of slopes at $T_{c}$
may provide even partial information on the microscopic symmetry of the order
parameter, this would be a worthy thing to do.

Thinking along these lines, we have examined the mixed $s+d$ order parameter
$\Omega(r)=\sqrt{1-r^{2}/2}+r\cos(2\varphi)$ such that $\Omega(0)$ corresponds
to the pure isotropic $s$-wave and $\Omega(\sqrt{2})$ is the pure $d$. We find
the remarkable one-to-one correspondence between presence or absence of nodes
and decrease or increase of the $H_{c2}$ slopes at $T_{c}$. Practically, this
is a highly useful observation, notwithstanding our oversimplified model.

There are various ways to introduce point-like uniform disorder into
superconductors. Perhaps the most promising and controllable are irradiation
with neutrons or electrons, see e.g. [3] and [7]. To our knowledge, the slope
$S$ in a nodal superconductor BaFe2(As,P)2 is decreasing up to large amounts
of disorder [7].

Hence, one of our major results is a novel experimentally-simple way to
distinguish between nodeless and nodal superconductivity. One has to examine
the rate of change of the slopes in samples of the same chemical composition
but with different amount of non-magnetic disorder. Such disorder can be
induced by ion implantation [18, 17], electron [2], proton [19], neutron [3,
20], or gamma [21] and even alpha particle irradiation [22]. If it decreases,
the system is likely nodal. If not, it is not.

A word of caution. It is quite possible that complex multi-band materials will
not follow our simple scheme, employing the generally accepted factorization
of temperature and angular variations of the order parameter. It is also
possible that other types of order parameters, say triplet, will not follow
either. However, our analysis is based on universal Ginzburg-Landau theory
and, hopefully, our conclusions may turn out robust.

###### Acknowledgements.

We thank M. Tanatar and S. Bud’ko for discussions. This work was supported by
the U.S. Department of Energy (DOE), Office of Science, Basic Energy Sciences,
Materials Science and Engineering Division. Ames Laboratory is operated for
the U.S. DOE by Iowa State University under contract DE-AC02-07CH11358.

## References

  * [1] S. Tokuta and A. Yamamoto, Enhanced Upper Critical Field in Co-Doped Ba122 Superconductors by Lattice Defect Tuning, APL Mater. 7, 111107 (2019).
  * [2] in preparation for submission. Experimental investigation of the $H_{c2}$ slope in BaK122 of different compositions.
  * [3] A. E. Karkin, T. Wolf, B. N. Goshchitskii, Superconducting properties of (Ba,K)Fe2As2 single crystals disordered with fast neutron irradiation. J. Phys.: Cond. Mat. 26, 275702 (2014), doi:10.1088/0953-8984/26/27/275702.
  * [4] K. Hashimoto, K. Cho, T. Shibauchi, S. Kasahara, Y. Mizukami, R. Katsumata, Y. Tsuruhara, T. Terashima, H. Ikeda, M. A. Tanatar, H. Kitano, N. Salovich, R. W. Giannetta, P. Walmsley, A. Carrington, R. Prozorov, and Y. Matsuda, A Sharp Peak of the Zero-Temperature Penetration Depth at Optimal Composition in BaFe2(As${}_{1\text{\textendash}x}$Px)2, Science (80) 336, 1554 (2012).
  * [5] A. I. Posazhennikova and M. V. Sadovski, The Ginzburg-Landau expansion and the slope of the upper critical field in disordered superconductors, Pis’ma Zh. Eksp. Teor. Fiz. 63, 347 (1996).
  * [6] A. I. Posazhennikova and M. V. Sadovski, The Ginzburg-Landau expansion and the slope of the upper critical field in superconductors with anisotropic normal-impurity scattering, Zh. Eksp. Teor. Fiz 112, 2124 (1997).
  * [7] A significant suppression of $T_{c}$ and of the slope of the upper critical field was observed in line-nodal iron pnictide, BaFe2(As,P)2. [Private communication].
  * [8] S. V. Pokrovsky, V. L. Pokrovsky,Density of states and order parameter in dirty anisotropic superconductors, Phys. Rev. B 54, 13275 (1996).
  * [9] D. Markowitz and L. P. Kadanoff, Effect of Impurities upon Critical Temperature of Anisotropic Superconductors, Phys. Rev. 131, 563 (1963).
  * [10] L. P. Gor’kov and T. K. Melik-Barkhudarov, Microscopic Derivation of the Ginzburg-Landau Equations for an Anisotropic Superconductor, Soviet Phys. JETP 18, 1031 (1964).
  * [11] E. Helfand and N.R. Werthamer, Temperature and Purity Dependence of the Superconducting Critical Field, $H_{c2}$. II, Phys. Rev. 147, 288 (1966).
  * [12] V. G. Kogan and R. Prozorov, Orbital Upper Critical Field and Its Anisotropy of Clean One- and Two-Band Superconductors, Rep. Prog. Phys. 75, 114502 (2012).
  * [13] L. A. Openov, Combined effect of nonmagnetic and magnetic scatterers on the critical temperatures of superconductors with different anisotropies of the gap, JETP Lett. 66, 661 (1997).
  * [14] V. G. Kogan, Pair breaking in iron pnictides, Phys. Rev. B 80, 214532 (2009).
  * [15] A. A. Abrikosov and L. P. Gor’kov, Contribution to the theory of superconducting alloys with paramagnetic impurities, Zh. Eksp. Teor. Fiz. 39, 1781 (1060) [Sov. Phys. JETP 12, 1243 (1961)].
  * [16] V. G. Kogan, R. Prozorov, Orbital upper critical field of type-II superconductors with pair breaking, Phys. Rev. B88, 024503 (2013).
  * [17] A. Antonov V, A. Ikonnikov V, D. Masterov V, A. N. Mikhaylov, S. Morozov V, Y. N. Nozdrin, S. A. Pavlov, A. E. Parafin, D. Tetel’baum I, S. S. Ustavschikov, V. K. Vasiliev, P. A. Yunin, D. A. Savinov, Critical-field slope reduction and upward curvature of the phase-transition lines of thin disordered superconducting YBa2Cu3O7-x films in strong magnetic fields, Physica C - Superconductivity and its Applications 568 (2020), doi:10.1016/j.physc.2019.1353581.
  * [18] R. H. T. Wilke, S. L. Bud’ko, P. C. Canfield, D. K. Finnemore, R. J. Suplinskas, S. T. Hannahs, Systematic Effects of Carbon Doping on the Superconducting Properties of MgB2. Phys. Rev. Lett. 92, 217003 (2004).
  * [19] J. Kim, N. Haberkorn, M. J. Graf, I. Usov, F. Ronning, L. Civale, E. Nazaretski, G. F. Chen, W. Yu, J. D. Thompson, R. Movshovich, Magnetic penetration-depth measurements of a suppressed superfluid density of superconducting Ca0.5Na0.5Fe2As2 single crystals by proton irradiation. Phys. Rev. B 86, 144509 (2012), doi:10.1103/PhysRevB.86.144509.
  * [20] R. H. T. Wilke, S. L. Bud’ko, P. C. Canfield, J. Farmer, S. T. Hannahs, Systematic study of the superconducting and normal-state properties of neutron-irradiated MgB2, Phys. Rev. B 73, 134512 (2006).
  * [21] A. A. E.-S. El-Hamalawy, M. M. El-Zaidia, E. A. G. E. A. Ghali, The Effects of Gamma-Radiation on the High Tc superconductors ErBa2Cu3O7-d, Jap. J. Appl. Phys. 31, 3529 (1992).
  * [22] C. Tarantini, K. Iida, N. Sumiya, M. Chihara, T. Hatano, H. Ikuta, R. K. Singh, N. Newman, D. C. Larbalestier, Effect of alpha-particle irradiation on a NdFeAs(O,F) thin film, Supercon. Sci. Tech. 31, 034002 (2018), doi:10.1088/1361-6668/aaa821.